Submission #632509

#TimeUsernameProblemLanguageResultExecution timeMemory
632509andrei_boacaPrinted Circuit Board (CEOI12_circuit)C++14
30 / 100
168 ms10048 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; typedef long long ll; typedef long double ld; int n; struct point { int x,y,ang; } v[100005],angle[100005]; bool comp(point a, point b) { return a.y*b.x<a.x*b.y; } map<pii,int> nrm; bool cmp(int a, int b) { if(v[a].ang!=v[b].ang) return v[a].ang<v[b].ang; return v[a].y<v[b].y; } bool use[100005],spec[100005]; int aib[100005],times[100005]; int lsb(int x) { return x&(-x); } void update(int poz,int val) { for(int i=poz;i<=n;i+=lsb(i)) aib[i]+=val; } int suma(int poz) { int rez=0; for(int i=poz;i>=1;i-=lsb(i)) rez+=aib[i]; return rez; } int cur=0; bool iseq(point a, point b) { return a.x==b.x&&a.y==b.y; } ll aria(point A, point B) { ll rez=1LL*A.x*B.y-1LL*A.y*B.x; rez=abs(rez); return rez; } bool intersect(point A, point B, point C) { if(iseq(A,C)||iseq(B,C)) return 0; ll a1=B.y-A.y; ll b1=A.x-B.x; ll c1=-a1*A.x-b1*A.y; ll a2=C.y; ll b2=-C.x; ll c2=0; ld coef=a2*b1-a1*b2; if(coef==0) return 0; ld y=ld(-a2*c1)/coef; ld x=ld(-b2*y)/a2; if(x>=min(A.x,B.x)&&x<=max(A.x,B.x)&&x<=C.x&&x>=0) if(y>=min(A.y,B.y)&&y<=max(A.y,B.y)&&y<=C.y&&y>=0) return 1; return 0; } bool checkgood(int i) { if(cur==0) return 1; point a=v[cur]; int lft=cur-1; if(lft<1) lft=n; point b=v[lft]; if(intersect(a,b,v[i])) return 0; int rgt=cur+1; if(rgt>n) rgt=1; b=v[rgt]; if(intersect(a,b,v[i])) return 0; return 1; } int main() { cin>>n; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y; v[i]={x,y,0}; int cmmdc=__gcd(x,y); x/=cmmdc; y/=cmmdc; angle[i]={x,y,0}; } sort(angle+1,angle+n+1,comp); // cout<<'\n'; for(int i=1;i<=n;i++) { pii a={angle[i].x,angle[i].y}; nrm[a]=i; } for(int i=1;i<=n;i++) { int cmmdc=__gcd(v[i].x,v[i].y); int xa=v[i].x/cmmdc,ya=v[i].y/cmmdc; v[i].ang=nrm[{xa,ya}]; } vector<int> ind; for(int i=1;i<=n;i++) ind.push_back(i); sort(ind.begin(),ind.end(),cmp); vector<int> sol; int nr=0; for(int i:ind) { nr++; bool good=checkgood(i); if(good) { cur=i; sol.push_back(i); } } sort(sol.begin(),sol.end()); cout<<sol.size()<<'\n'; for(int i:sol) cout<<i<<' '; return 0; }

Compilation message (stderr)

circuit.cpp: In function 'bool intersect(point, point, point)':
circuit.cpp:63:8: warning: unused variable 'c2' [-Wunused-variable]
   63 |     ll c2=0;
      |        ^~
#Verdict Execution timeMemoryGrader output
Fetching results...