제출 #487107

#제출 시각아이디문제언어결과실행 시간메모리
487107Cross_RatioPrinted Circuit Board (CEOI12_circuit)C++14
100 / 100
54 ms8260 KiB
#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 <<' ';
}

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

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 timeMemoryGrader output
Fetching results...