#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)/ld(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
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 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 |
512 KB |
Output is correct |
| 4 |
Correct |
4 ms |
624 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
1292 KB |
Output isn't correct |
| 6 |
Incorrect |
14 ms |
1316 KB |
Output isn't correct |
| 7 |
Incorrect |
28 ms |
2236 KB |
Output isn't correct |
| 8 |
Incorrect |
13 ms |
1100 KB |
Output isn't correct |
| 9 |
Correct |
8 ms |
980 KB |
Output is correct |
| 10 |
Incorrect |
14 ms |
1236 KB |
Output isn't correct |
| 11 |
Incorrect |
15 ms |
1340 KB |
Output isn't correct |
| 12 |
Correct |
20 ms |
2180 KB |
Output is correct |
| 13 |
Incorrect |
39 ms |
3236 KB |
Output isn't correct |
| 14 |
Incorrect |
39 ms |
4044 KB |
Output isn't correct |
| 15 |
Correct |
52 ms |
4880 KB |
Output is correct |
| 16 |
Execution timed out |
133 ms |
9432 KB |
Time limit exceeded |
| 17 |
Execution timed out |
183 ms |
10088 KB |
Time limit exceeded |
| 18 |
Runtime error |
59 ms |
5060 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
58 ms |
5068 KB |
Execution killed with signal 11 |
| 20 |
Execution timed out |
133 ms |
8420 KB |
Time limit exceeded |
