# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
633358 | andrei_boaca | Printed Circuit Board (CEOI12_circuit) | C++14 | 1088 ms | 6812 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>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
struct point
{
ll x,y,ang,poz;
} v[100005];
bool byang(int q, int t)
{
point a=v[q];
point b=v[t];
if(a.y*b.x!=a.x*b.y)
return a.y*b.x<a.x*b.y;
return a.x<b.x;
}
bool iseq(point A, point B)
{
return A.x==B.x&&A.y==B.y;
}
bool intersect(point A, point B, point C)
{
if(iseq(A,C)||iseq(B,C))
return 1;
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<C.x&&y<C.y&&x>0&&y>0)
return 1;
return 0;
}
bool bylin(int q,int t)
{
point a=v[q];
int nxt=q+1;
if(nxt>n)
nxt=1;
point b=v[nxt];
point c=v[t];
nxt=t+1;
if(nxt>n)
nxt=1;
point d=v[nxt];
bool isC=intersect(a,b,c);
bool isD=intersect(a,b,d);
if(isC==0&&isD==0)
return 0;
if(isC==1&&isD==1)
return 1;
bool isA=intersect(c,d,a);
bool isB=intersect(c,d,b);
if(isA==0&&isB==0)
return 1;
if(isA==1&&isB==1)
return 0;
return 0;
}
int fst[100005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
v[i].poz=i;
}
vector<int> ind;
for(int i=1;i<=n;i++)
ind.push_back(i);
sort(ind.begin(),ind.end(),byang);
int nr=0;
for(int i=0;i<ind.size();i++)
{
if(i==0)
nr++;
else
{
point a=v[ind[i-1]];
point b=v[ind[i]];
if(a.y*b.x!=a.x*b.y)
nr++;
}
v[ind[i]].ang=nr;
}
ind.clear();
for(int i=1;i<=n;i++)
ind.push_back(i);
sort(ind.begin(),ind.end(),bylin);
for(int i:ind)
{
int st=v[i].ang;
int nxt=i+1;
if(nxt>n)
nxt=1;
int dr=v[nxt].ang;
if(st>dr)
swap(st,dr);
for(int j=st;j<=dr;j++)
if(fst[j]==0)
fst[j]=i;
}
vector<int> sol;
for(int i=1;i<=n;i++)
{
int ang=v[i].ang;
//cout<<fst[ang]<<' ';
int prv=i-1;
if(i==1)
prv=n;
if(fst[ang]!=i&&fst[ang]!=prv)
continue;
sol.push_back(i);
}
sort(sol.begin(),sol.end());
cout<<sol.size()<<'\n';
for(int i:sol)
cout<<i<<' ';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |