oj.uz

답안 #348191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348191 2021-01-14T10:43:19 Z Harry464 Fence (CEOI08_fence) C++14
100 / 100
 4 ms 620 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;

vector <bool> te(1000,false);
vector <vector <bool> > adjl(1000, te);

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());

    //upper hull
    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);
    }
    //lower hull
    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]);

    ll bv = tacke.size();

    //tacke unutar hulla
    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 = (t[i].first-ax)*(by - ay) - (t[i].second - ay)*(bx - ax);

            if (val < 0)
                jeste = false;
        }

        for (int j = lh.size() - 1; j >= 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 = (t[i].first-ax)*(by - ay) - (t[i].second - ay)*(bx - ax);

            if (val < 0)
                jeste = false;
        }

        if (jeste)
            odg.push_back(i);
    }

    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 = (t[odg[k]].first-ax)*(by - ay) - (t[odg[k]].second - ay)*(bx - ax);

               if (val < 0)
                 jed = false;
            }

            if (jed)
                adjl[i][j] = true;
        }
    }

    ll shortest = 10000000;

    vector <ll> tem(n,1000000000);
    vector <vector<ll> > put(n,tem);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
          if (adjl[i][j])
           put[i][j] = 1;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                put[i][k] = min(put[i][k], put[i][j] + put[j][k]);


    for (int i = 0; i < n; i++)
        shortest = min(shortest, put[i][i]);
    if (odg.size() == 0){
        cout << m*111;
        return 0;
    }
    cout << shortest*20 + (m - odg.size())*111;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct