#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=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;
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];
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 intersect(point, point, point)':
circuit.cpp:34:8: warning: unused variable 'c2' [-Wunused-variable]
34 | ll c2=0;
| ^~
circuit.cpp: In function 'int main()':
circuit.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | 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 |
Correct |
4 ms |
468 KB |
Output is correct |
| 4 |
Correct |
4 ms |
468 KB |
Output is correct |
| 5 |
Incorrect |
27 ms |
724 KB |
Output isn't correct |
| 6 |
Incorrect |
22 ms |
756 KB |
Output isn't correct |
| 7 |
Incorrect |
59 ms |
1176 KB |
Output isn't correct |
| 8 |
Incorrect |
15 ms |
596 KB |
Output isn't correct |
| 9 |
Correct |
25 ms |
860 KB |
Output is correct |
| 10 |
Incorrect |
21 ms |
876 KB |
Output isn't correct |
| 11 |
Incorrect |
24 ms |
724 KB |
Output isn't correct |
| 12 |
Correct |
35 ms |
1160 KB |
Output is correct |
| 13 |
Execution timed out |
125 ms |
1500 KB |
Time limit exceeded |
| 14 |
Execution timed out |
118 ms |
2000 KB |
Time limit exceeded |
| 15 |
Correct |
95 ms |
2352 KB |
Output is correct |
| 16 |
Execution timed out |
197 ms |
4360 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1054 ms |
4352 KB |
Time limit exceeded |
| 18 |
Execution timed out |
398 ms |
9372 KB |
Time limit exceeded |
| 19 |
Execution timed out |
379 ms |
9392 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1087 ms |
9416 KB |
Time limit exceeded |
