#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
int x[100005],y[100005];
int ord[100005]; //order of the point
li dot(int a, int b, int c, int d)
{
return (li)a*d-(li)b*c;
}
struct mojsort
{
bool operator() (pair<pii,int> x, pair<pii,int> y)
{
return dot(x.xx.xx,x.xx.yy,y.xx.xx,y.xx.yy)>0;
}
};
int N;
int fwt[100005];
void add(int i, int x)
{
for (;i<=N;i+=(i&-i)) fwt[i]+=x;
}
int pre(int i)
{
int ret=0;
for (;i;i-=(i&-i)) ret+=fwt[i];
return ret;
}
main()
{
FAST;
int n; cin>>n;
ff(i,0,n) cin>>x[i]>>y[i];
vector<pair<li,int>> tacke;
ff(i,0,n) tacke.push_back({-((li)x[i]*x[i] + (li)y[i]*y[i]),i});
sort(all(tacke));
vector<pair<li,int>> duzi;
ff(i,0,n)
{
int j=(i+1)%n;
li d=max((li)x[i]*x[i]+(li)y[i]*y[i],(li)x[j]*x[j]+(li)y[j]*y[j]);
duzi.push_back({-d,i});
}
sort(all(duzi));
vector<pair<pii,int>> uglovi;
ff(i,0,n) uglovi.push_back({{x[i],y[i]},i});
sort(all(uglovi),mojsort());
int idx=0;
ff(i,0,n)
{
if (i==0 || dot(uglovi[i-1].xx.xx,uglovi[i-1].xx.yy,uglovi[i].xx.xx,uglovi[i].xx.yy)) ++idx;
ord[uglovi[i].yy]=idx;
}
N=idx;
vector<int> ans;
while (!tacke.empty() && !duzi.empty())
{
if (tacke.back().xx >= duzi.back().xx)
{
if (pre(ord[tacke.back().yy])==0)
{
ans.pb(tacke.back().yy+1);
}
tacke.popb();
}
else
{
int i=duzi.back().yy;
int j=(i+1)%n;
int l=ord[i];
int r=ord[j];
if (l>r) swap(l,r);
add(l,1);
add(r+1,-1);
duzi.popb();
}
}
sort(all(ans));
cout<<(int)ans.size()<<"\n";
for (auto it : ans) cout<<it<<" ";
}
Compilation message
circuit.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
68 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
3 ms |
604 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
1308 KB |
Output isn't correct |
| 6 |
Incorrect |
5 ms |
1304 KB |
Output isn't correct |
| 7 |
Incorrect |
12 ms |
2396 KB |
Output isn't correct |
| 8 |
Incorrect |
4 ms |
1116 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
1116 KB |
Output isn't correct |
| 10 |
Incorrect |
5 ms |
1308 KB |
Output isn't correct |
| 11 |
Incorrect |
5 ms |
1392 KB |
Output isn't correct |
| 12 |
Incorrect |
7 ms |
2140 KB |
Output isn't correct |
| 13 |
Incorrect |
13 ms |
2908 KB |
Output isn't correct |
| 14 |
Incorrect |
15 ms |
3932 KB |
Output isn't correct |
| 15 |
Incorrect |
19 ms |
4628 KB |
Output isn't correct |
| 16 |
Incorrect |
34 ms |
9048 KB |
Output isn't correct |
| 17 |
Incorrect |
46 ms |
9208 KB |
Output isn't correct |
| 18 |
Runtime error |
13 ms |
3416 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
13 ms |
3416 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
14 ms |
3564 KB |
Execution killed with signal 11 |
