Submission #120375

#TimeUsernameProblemLanguageResultExecution timeMemory
120375tmwilliamlin168Printed Circuit Board (CEOI12_circuit)C++14
10 / 100
17 ms4676 KiB
#include <bits/stdc++.h> using namespace std; int in() { char c=0; while(c<'0'||c>'9') c=getchar_unlocked(); int r=0; while(c>='0'&&c<='9') { r=r*10+c-'0'; c=getchar_unlocked(); } return r; } void out(int x) { int c=0, r=0; for(; x%10==0; ++c, x/=10); for(; x; r=r*10+x%10, x/=10); for(; r; r/=10) putchar_unlocked('0'+r%10); while(c--) putchar_unlocked(' '); } const int mxN=2e5; int n, l, r; long long x[mxN+1], y[mxN+1]; vector<int> v, s; bool b[mxN]; int main() { auto cp=[](int a, int b, int c) { return (y[c]-y[a])*(x[b]-x[a])-(y[b]-y[a])*(x[c]-x[a]); }; n=in(); for(int i=0; i<n; ++i) { x[i]=in(), y[i]=in(); if(!i||cp(n, l, i)>0||!cp(n, l, i)&&x[i]<x[l]) l=i; if(!i||cp(n, r, i)<0||!cp(n, r, i)&&x[i]<x[r]) r=i; } int ic=cp((l+n-1)%n, l, (l+1)%n)>0?1:n-1; for(; l^r; l=(l+ic)%n) v.push_back(l); v.push_back(r); s={0, 1}; for(int i=2; i<v.size(); ++i) { auto ul=[&]() { while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<=0) s.pop_back(); for(int j=i, c=cp(n, v[s.back()], v[i])<0; cp(n, v[s.back()], v[i])>=0||!c; ++i) { if(i^j?cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0:cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0) ++c; if(cp(n, v[j], v[i])<0&&cp(n, v[j], v[i+1])>=0&&cp(v[i], v[i+1], v[j])<0) --c; } }; if(!cp(n, v[i-1], v[i])&&(cp(n, v[i-2], v[i-1])<0)==(cp(v[i-2], v[i-1], v[i])<0)) s.pop_back(); else if(cp(n, v[i-1], v[i])<=0&&cp(n, v[i-2], v[i-1])>0&&cp(v[i-2], v[i-1], v[i])<0) { while(cp(n, v[s.back()], v[i])<=0) ++i; s.pop_back(); ul(); } else if(cp(n, v[i-1], v[i])>0&&(cp(n, v[i-2], v[i-1])>=0||cp(v[i-2], v[i-1], v[i])<0)) ul(); else if(cp(n, v[i-1], v[i])>=0) while(cp(n, v[s.back()], v[i])>=0) ++i; s.push_back(i); } out(s.size()); putchar_unlocked('\n'); for(int a : s) b[v[a]]=1; for(int i=0; i<n; ++i) { if(b[i]) { out(i+1); putchar_unlocked(' '); } } }

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:39:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(!i||cp(n, l, i)>0||!cp(n, l, i)&&x[i]<x[l])
                         ~~~~~~~~~~~~^~~~~~~~~~~
circuit.cpp:41:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(!i||cp(n, r, i)<0||!cp(n, r, i)&&x[i]<x[r])
                         ~~~~~~~~~~~~^~~~~~~~~~~
circuit.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=2; i<v.size(); ++i) {
               ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...