Submission #487107

# Submission time Handle Problem Language Result Execution time Memory
487107 2021-11-14T10:26:17 Z Cross_Ratio Printed Circuit Board (CEOI12_circuit) C++14
100 / 100
54 ms 8260 KB
#include <bits/stdc++.h>
#define int long long
using namespace std;
int X[200005];
int Y[200005];
int cmp(int x, int y) { // x < y : True
    int k = Y[y]*X[x]-Y[x]*X[y];
    if(k > 0) return 1;
    else if(k == 0) return 0;
    return -1;
}
int ccw(int x, int y, int m) {
    int x1 = X[x]-X[y];
    int y1 = Y[x]-Y[y];
    int x2 = X[m]-X[x];
    int y2 = Y[m]-Y[x];
    return x1*y2-x2*y1;
}
int ccw2(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    int op = a.first*b.second + b.first*c.second + c.first*a.second;
    op -= (a.second*b.first + b.second*c.first + c.second*a.first);
    if (op > 0)return 1;
    else if (op == 0)return 0;
    else return -1;
}
int isIntersect(pair<pair<int, int>, pair<int, int>> x, pair<pair<int, int>, pair<int, int>> y) {
    pair<int, int> a = x.first;
    pair<int, int> b = x.second;
    pair<int, int> c = y.first;
    pair<int, int> d = y.second;
    int ab = ccw2(a, b, c)*ccw2(a, b, d);
    int cd = ccw2(c, d, a)*ccw2(c, d, b);
    if (ab == 0 && cd == 0) {
        if (a > b)swap(a, b);
        if (c > d)swap(c, d);
        return c <= b&&a <= d;
    }
    return ab <= 0 && cd <= 0;
}
typedef pair<int,int> P;
 
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i;
    int N;
    cin >> N;
    for(i=0;i<N;i++) cin >> X[i] >> Y[i];
    if(N <= 1000) {
        vector<int> ans;
        for(i=0;i<N;i++) {
            bool isPos = true;
            for(int j = 0; j < N; j++) {
                if(i==j||i==(j+1)%N) continue;
                if(isIntersect(pair<P,P>(P(0,0),P(X[i],Y[i])),pair<P,P>(P(X[j],Y[j]),P(X[(j+1)%N],Y[(j+1)%N])))) {
                    isPos = false;
                    break;
                }
            }
            if(isPos) ans.push_back(i+1);
        }
        cout << ans.size() << '\n';
        for(i=0;i<ans.size();i++) cout << ans[i] << ' ';
        return 0;
    }
    __int128_t cnt = 0;
    cnt += X[N-1]*Y[0]-X[0]*Y[N-1];
    for(i=0;i<N-1;i++) {
        cnt += X[i]*Y[i+1]-X[i+1]*Y[i];
    }
    int st, en;
    st = en = 0;
    for(i=1;i<N;i++) {
        int k1 = Y[st] * X[i] - X[st] * Y[i];
        int k2 = Y[en] * X[i] - X[en] * Y[i];
        bool isSmall = k1 != 0 ? k1 > 0 : X[st] > X[i];
        bool isBig = k2 != 0 ? k2 < 0 : X[en] > X[i];
        if(isSmall) st = i;
        if(isBig) en = i;
    }
    //cout << st << ' ' << en << '\n';
    vector<int> A;
    if(cnt < 0) {
        //cout << "Clockwise\n";
        if(st > en) en += N;
        for(i=st;i<=en;i++) {
            A.push_back(i % N);
            //cout << i % N << ' ';
        }
        //cout << '\n';
    }
    else {
        //cout << "CounterClockwise\n";
        if(st < en) st += N;
        for(i=st;i>=en;i--) {
            A.push_back(i % N);
            //cout << i % N << ' ';
        }
        //cout << '\n';
    }
    stack<int> S;
    for(i=0;i<A.size();i++) {
        if(S.empty()) {
            S.push(i);
            continue;
        }
        int k = Y[A[i]]*X[A[S.top()]]-X[A[i]]*Y[A[S.top()]];
        //cout << i << ' ' << A[i] << ' ' << A[S.top()] << " : " << k << '\n';
        if(k <= 0) {
            //cout << "Case " << i << '\n';
            int n1 = S.top();
            //cout << n1 << '\n';
            if(ccw(A[n1], A[n1-1], A[i])<0) {
                //cout << "CCW case\n";
                while(i < A.size() &&(cmp(A[i],A[n1])==1
                    ||(!cmp(A[i],A[n1])&&X[A[i]]>X[A[n1]]))) {
                      i++;
                }
                if(i < A.size()) S.push(i);
            }
            else {
                //cout << "None Case\n";
                while(true) {
                    while(cmp(A[i], A[S.top()])==1
            ||(!cmp(A[i], A[S.top()])&&X[A[i]] < X[A[S.top()]])) {
                        S.pop();
                    }
                    if(cmp(A[i], A[i+1])>=0) {
                        if(!ccw(A[i-2], A[i-1], A[i])) {
                            int j = i;
                            while(cmp(A[j],A[i])==1||
                        (!cmp(A[j],A[i])&&X[A[j]]<X[A[i]])) {
                                i++;
                            }
                        }
                        else {
                            break;
                        }
                    }
                    i++;
                    if(i == A.size()) break;
                }
                S.push(i);
            }
        }
        else S.push(i);
        /*
        stack<int> S2 = S;
        while(!S2.empty()) {
            cout << A[S2.top()]+1 <<' ';
            S2.pop();
        }
        cout << '\n';
        */
    }
    vector<int> ans;
    while(!S.empty()) {
        ans.push_back(A[S.top()]);
        S.pop();
    }
    cout << ans.size() << '\n';
    sort(ans.begin(),ans.end());
    for(i=0;i<ans.size();i++) cout << ans[i]+1 <<' ';
}

Compilation message

circuit.cpp: In function 'int main()':
circuit.cpp:64:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(i=0;i<ans.size();i++) cout << ans[i] << ' ';
      |                 ~^~~~~~~~~~~
circuit.cpp:103:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(i=0;i<A.size();i++) {
      |             ~^~~~~~~~~
circuit.cpp:116:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |                 while(i < A.size() &&(cmp(A[i],A[n1])==1
      |                       ~~^~~~~~~~~~
circuit.cpp:120:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |                 if(i < A.size()) S.push(i);
      |                    ~~^~~~~~~~~~
circuit.cpp:142:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |                     if(i == A.size()) break;
      |                        ~~^~~~~~~~~~~
circuit.cpp:164:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for(i=0;i<ans.size();i++) cout << ans[i]+1 <<' ';
      |             ~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 328 KB Output is correct
3 Correct 1 ms 488 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 6 ms 1100 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 4 ms 1228 KB Output is correct
13 Correct 5 ms 1488 KB Output is correct
14 Correct 7 ms 1740 KB Output is correct
15 Correct 8 ms 2256 KB Output is correct
16 Correct 17 ms 4172 KB Output is correct
17 Correct 17 ms 3808 KB Output is correct
18 Correct 36 ms 8000 KB Output is correct
19 Correct 54 ms 8128 KB Output is correct
20 Correct 40 ms 8260 KB Output is correct