#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[200005];
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;
}
int 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=a1*b2-a2*b1;
if(coef==0)
return 0;
ld x=ld(c2*b1-c1*b2)/coef;
ld y=ld(-c1-a1*x)/ld(b1);
if(x<=C.x&&y<=C.y&&x>0&&y>0)
return 1;
if(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];
if(a.ang==b.ang&&a.ang==c.ang&&a.ang==d.ang)
{
int xa=min(a.x,b.x);
if(xa<c.x&&xa<d.x)
return 1;
return 0;
}
int isC=intersect(a,b,c);
int isD=intersect(a,b,d);
if(isC==0&&isD==0)
return 0;
if(isC==1&&isD==1)
return 1;
int isA=intersect(c,d,a);
int isB=intersect(c,d,b);
if(isA==0&&isB==0)
return 1;
if(isA==1&&isB==1)
return 0;
return 0;
}
int fst[200005];
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
circuit.cpp: In function 'int main()':
circuit.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i=0;i<ind.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Execution timed out |
168 ms |
452 KB |
Time limit exceeded |
| 4 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 5 |
Incorrect |
29 ms |
752 KB |
Output isn't correct |
| 6 |
Incorrect |
22 ms |
724 KB |
Output isn't correct |
| 7 |
Incorrect |
61 ms |
1172 KB |
Output isn't correct |
| 8 |
Incorrect |
17 ms |
676 KB |
Output isn't correct |
| 9 |
Correct |
27 ms |
716 KB |
Output is correct |
| 10 |
Incorrect |
24 ms |
756 KB |
Output isn't correct |
| 11 |
Incorrect |
26 ms |
808 KB |
Output isn't correct |
| 12 |
Correct |
38 ms |
1108 KB |
Output is correct |
| 13 |
Execution timed out |
134 ms |
1620 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1089 ms |
1892 KB |
Time limit exceeded |
| 15 |
Correct |
98 ms |
2384 KB |
Output is correct |
| 16 |
Execution timed out |
228 ms |
4372 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1088 ms |
4364 KB |
Time limit exceeded |
| 18 |
Execution timed out |
435 ms |
8376 KB |
Time limit exceeded |
| 19 |
Execution timed out |
488 ms |
8340 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1085 ms |
8264 KB |
Time limit exceeded |
