제출 #348129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348129		Harry464	Fence (CEOI08_fence)	C++14	10 / 100	5 ms	620 KiB

fence

#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;

vector <vector <ll> > adjl(10000);

int main()
{
    ll n, m;
    cin >> n >> m;
    vector <pair<ll,ll> > h(n);
    vector <pair<ll,ll> > t(m);
    for (int i = 0; i < n; i++)
      cin >> h[i].first >> h[i].second;
    for (int i = 0; i < m; i++)
      cin >> t[i].first >> t[i].second;
    vector <ll> uh;
    vector <ll> lh;
    sort(h.begin(), h.end());
    for (int i = 0; i < n; i++){
        if (uh.size() < 2){
            uh.push_back(i);
            continue;
        }
        ll cx = h[i].first, cy = h[i].second;
        ll s = uh.size();
        while (s >= 2){
            ll bx = h[uh[s-1]].first, by = h[uh[s-1]].second;
            ll ax = h[uh[s-2]].first, ay = h[uh[s-2]].second;
            ll por = (bx-ax)*(cy-ay) - (cx-ax)*(by-ay);
            if (por > 0)
                uh.pop_back(), s--;
            else
                break;
        }
        uh.push_back(i);
    }
    for (int i = 0; i < n; i++){
        if (lh.size() < 2){
            lh.push_back(i);
            continue;
        }
        ll cx = h[i].first, cy = h[i].second;
        ll s = lh.size();
        while (s >= 2){
            ll bx = h[lh[s-1]].first, by = h[lh[s-1]].second;
            ll ax = h[lh[s-2]].first, ay = h[lh[s-2]].second;
            ll por = (bx-ax)*(cy-ay) - (cx-ax)*(by-ay);
            if (por < 0)
                lh.pop_back(), s--;
            else
                break;
        }
        lh.push_back(i);
    }
    vector <ll> tacke;
    for (int i = 0; i < uh.size(); i++)
        tacke.push_back(uh[i]);
    for (int i = lh.size() - 2; i >= 1; i--)
        tacke.push_back(lh[i]);
    vector <ll> odg;
    for (int i = 0; i < m; i++){
        bool jeste = true;
        for (int j = 0; j < uh.size() - 1; j++){
            ll bx = h[uh[j+1]].first, by = h[uh[j+1]].second;
            ll ax = h[uh[j]].first, ay = h[uh[j]].second;
            ll val = (bx-ax)*(t[i].second - ay) - (by - ay)*(t[i].first - ax);
            if (val > 0)
                jeste = false;
        }
        for (int j = 0; j < lh.size() - 1; j++){
            ll bx = h[lh[j+1]].first, by = h[lh[j+1]].second;
            ll ax = h[lh[j]].first, ay = h[lh[j]].second;
            ll val = (bx-ax)*(t[i].second - ay) - (by - ay)*(t[i].first - ax);
            if (val < 0)
                jeste = false;
        }
        if (jeste)
            odg.push_back(i);
    }
    ll bv = tacke.size();
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (i == j)
                continue;
            ll bx = h[j].first, by = h[j].second;
            ll ax = h[i].first, ay = h[i].second;
            bool jed = true;
            for (int k = 0; k < odg.size(); k++){
               ll val = (bx-ax)*(t[odg[k]].second - ay) - (by - ay)*(t[odg[k]].second - ax);
               if (val > 0)
                 jed = false;
            }
            if (jed)
                adjl[i].push_back(j);
        }
    }
    ll shortest = 10000000;
    for (int i = 0; i < n; i++){
        priority_queue <pair<ll, ll>> bfs;
        vector <ll> vis(n, 10000000);
        bfs.push(make_pair(0,i));
        while(bfs.size()){
            ll u = bfs.top().second, c = -bfs.top().first;
            bfs.pop();
            for (int j = 0; j < adjl[u].size(); j++){
                ll v = adjl[u][j];
                if (v == i){
                    vis[v] = min(vis[v], c + 1);
                    continue;
                }
                if (c + 1 < vis[v])
                    vis[v] = c + 1, bfs.push(make_pair(-(c + 1), v));
            }
        }
        shortest = min(shortest, vis[i]);
    }
    cout << shortest*20 + (m - odg.size())*111;
}

컴파일 시 표준 에러 (stderr) 메시지

fence.cpp: In function 'int main()':
fence.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < uh.size(); i++)
      |                     ~~^~~~~~~~~~~
fence.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j = 0; j < uh.size() - 1; j++){
      |                         ~~^~~~~~~~~~~~~~~
fence.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int j = 0; j < lh.size() - 1; j++){
      |                         ~~^~~~~~~~~~~~~~~
fence.cpp:97:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for (int k = 0; k < odg.size(); k++){
      |                             ~~^~~~~~~~~~~~
fence.cpp:114:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for (int j = 0; j < adjl[u].size(); j++){
      |                             ~~^~~~~~~~~~~~~~~~
fence.cpp:89:8: warning: unused variable 'bv' [-Wunused-variable]
   89 |     ll bv = tacke.size();
      |        ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10