Submission #348241

#	Time	Username	Problem	Language	Result	Execution time	Memory
348241		Uncreative	Fence (CEOI08_fence)	C++14	100 / 100	4 ms	508 KiB

fence

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;

const int maxn = 105;

int ccw(int ax, int ay, int bx, int by, int cx, int cy){
    return ax * (by - cy) + bx * (cy - ay) + cx * (ay - by);
}



int fx[maxn];
int fy[maxn];

int tx[maxn];
int ty[maxn];

int ccwf(int a, int b, int c){
    return fx[a] * (fy[b] - fy[c]) + fx[b] * (fy[c] - fy[a]) + fx[c] * (fy[a] - fy[b]);
}

const int inf = 10000000;
int mat[maxn][maxn];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    map<pair<int, int>, int> mapa;
    vector<int> ind;
    vector<int> gh;
    vector<int> dh;
    vector<int> hull;

    for (int i = 1; i <= n; i++){
        cin >> fx[i] >> fy[i];
        if (mapa[make_pair(fx[i], fy[i])] == 0){
            mapa[make_pair(fx[i], fy[i])] = i;
        }
    }

    for (int i = 1; i <= m; i++){
        cin >> tx[i] >> ty[i];
    }

    for (auto it: mapa){
        ind.push_back(it.second);
    }

    for (int i = 0; i < ind.size(); i++){
        while (gh.size() >= 2 && ccwf(gh[(int)gh.size() - 2], gh[(int)gh.size() - 1], ind[i]) > 0){
            gh.pop_back();
        }
        gh.push_back(ind[i]);
    }
    gh.pop_back();
    reverse(ind.begin(), ind.end());

    for (int i = 0; i < ind.size(); i++){
        while (dh.size() >= 2 && ccwf(dh[(int)dh.size() - 2], dh[(int)dh.size() - 1], ind[i]) > 0){
            dh.pop_back();
        }
        dh.push_back(ind[i]);
    }
    dh.pop_back();

    for (int i = 0; i < gh.size(); i++){
        hull.push_back(gh[i]);
    }
    for (int i = 0; i < dh.size(); i++){
        hull.push_back(dh[i]);
    }
    /*for (int i = 0; i < hull.size(); i++){
        cout << hull[i] << " ";
    }
    cout << "\n";*/
    vector<int> dt;

    for (int i = 1; i <= m; i++){
        int r = 0;
        //cout << "I " << i << "\n";
        int t = hull[(int)hull.size() - 1], t2 = hull[0];
        if (ccw(fx[t], fy[t], tx[i], ty[i], fx[t2], fy[t2]) < 0){
            r = 1;
        }
        //cout << r << "\n";
        for (int j = 0; j < (int)hull.size() - 1; j++){
            int t = hull[j];
            int t2 = hull[j + 1];
            if (ccw(fx[t], fy[t], tx[i], ty[i], fx[t2], fy[t2]) < 0){
                r = 1;
            }
            //cout << r << "\n";
        }

        if (r == 0){
            dt.push_back(i);
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            mat[i][j] = inf;
        }
    }
    for (int i = 1; i <= n - 1; i++){
        for (int j = i + 1; j <= n; j++){

            int a = i;
            int b = j;
            int r = 0;
            for (int k = 0; k < dt.size(); k++){
                if (ccw(fx[a], fy[a], tx[dt[k]], ty[dt[k]], fx[b], fy[b]) > 0){
                    r = 1;
                }
            }
            if (r == 0){
                mat[a][b] = 1;
            }

            r = 0; a = j; b = i;
            for (int k = 0; k < dt.size(); k++){
                if (ccw(fx[a], fy[a], tx[dt[k]], ty[dt[k]], fx[b], fy[b]) > 0){
                    r = 1;
                }
            }
            if (r == 0){
                mat[a][b] = 1;
            }
        }
    }

    for (int k = 1; k <= n; k++){
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (mat[i][k] + mat[k][j] < mat[i][j]){
                    mat[i][j] = mat[i][k] + mat[k][j];
                }
            }
        }
    }
    int sol = inf;
    for (int i = 1; i <= n; i++){
        sol = min(sol, mat[i][i]);
    }
    //cout << dt.size() << endl;
    //cout << sol << " " << (m - (int)dt.size()) << endl;
    if (dt.size() == 0){
        cout << m * 111 << "\n";
    }
    else {
        cout << 20 * sol + 111 * (m - (int)dt.size());
    }
}

Compilation message (stderr)

fence.cpp: In function 'int main()':
fence.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < ind.size(); i++){
      |                     ~~^~~~~~~~~~~~
fence.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < ind.size(); i++){
      |                     ~~^~~~~~~~~~~~
fence.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < gh.size(); i++){
      |                     ~~^~~~~~~~~~~
fence.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < dh.size(); i++){
      |                     ~~^~~~~~~~~~~
fence.cpp:116:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for (int k = 0; k < dt.size(); k++){
      |                             ~~^~~~~~~~~~~
fence.cpp:126:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             for (int k = 0; k < dt.size(); k++){
      |                             ~~^~~~~~~~~~~

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