| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 487107 | Cross_Ratio | Printed Circuit Board (CEOI12_circuit) | C++14 | 54 ms | 8260 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||