#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define getchar_unlocked getchar
#define putchar_unlocked putchar
int in() {
char c=0;
while(c<'0'||c>'9')
c=getchar_unlocked();
int r=0;
while(c>='0'&&c<='9') {
r=r*10+c-'0';
c=getchar_unlocked();
}
return r;
}
void out(int x) {
int c=0, r=0;
for(; x%10==0; ++c, x/=10);
for(; x; x/=10)
r=r*10+x%10;
for(; r; r/=10)
putchar_unlocked(r%10+'0');
while(c--)
putchar_unlocked('0');
}
const int mxN=2e5;
int n, b[mxN], c[mxN+1], e1[mxN], e2[mxN], a1;
array<ll, 2> a[mxN+1];
vector<int> va[mxN], vr[mxN], vp[mxN];
bool tr[mxN], ans[mxN];
bool cw(int x, int y, int z) {
return (a[z][1]-a[x][1])*(a[y][0]-a[x][0])<(a[y][1]-a[x][1])*(a[z][0]-a[x][0]);
}
bool pcmp(const int &i, const int &j) {
return a[i][1]*a[j][0]<a[j][1]*a[i][0];
}
struct scmp {
bool operator()(const int &i, const int &j) const {
if(tr[i])
return 1;
if(tr[j])
return 0;
if(e1[i]==e1[j])
return c[e2[i]]<c[e2[j]]?cw(e1[j], e2[j], e2[i]):!cw(e1[i], e2[i], e2[j]);
return c[e1[i]]<c[e1[j]]?!cw(e1[i], e2[i], e1[j]):cw(e1[j], e2[j], e1[i]);
}
};
priority_queue<int, vector<int>, scmp> pq;
int main() {
n=in();
for(int i=0; i<n; ++i)
a[i]={in(), in()};
a[n]=a[0];
iota(b, b+n, 0);
sort(b, b+n, pcmp);
for(int i=0, j=0; i<n; i=j) {
for(; j<n&&a[b[i]][1]*a[b[j]][0]==a[b[j]][1]*a[b[i]][0]; ++j) {
c[b[j]]=i;
vp[c[b[j]]].push_back(b[j]);
}
}
c[n]=c[0];
for(int i=0; i<n; ++i) {
e1[i]=i;
e2[i]=i+1;
if(c[e2[i]]<c[e1[i]])
swap(e1[i], e2[i]);
if(c[e1[i]]<c[e2[i]]) {
va[c[e1[i]]].push_back(i);
vr[c[e2[i]]].push_back(i);
}
}
for(int i=0; i<n; ++i) {
for(int j : vr[i])
tr[j]=1;
for(int j : va[i])
pq.push(j);
while(pq.size()&&tr[pq.top()])
pq.pop();
int mj=-1;
for(int j : vp[i])
if(mj<0||a[j][0]+a[j][1]<a[mj][0]+a[mj][1])
mj=j;
if(~mj&&(!pq.size()||!cw(e1[pq.top()], e2[pq.top()], mj)))
ans[mj]=1;
}
for(int i=0; i<n; ++i)
a1+=ans[i];
out(a1);
putchar_unlocked('\n');
for(int i=0; i<n; ++i) {
if(ans[i]) {
out(i+1);
putchar_unlocked(' ');
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14488 KB |
Output isn't correct |
| 2 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14848 KB |
Output is correct |
| 4 |
Correct |
17 ms |
14976 KB |
Output is correct |
| 5 |
Incorrect |
20 ms |
15616 KB |
Output isn't correct |
| 6 |
Incorrect |
20 ms |
15616 KB |
Output isn't correct |
| 7 |
Incorrect |
26 ms |
16764 KB |
Output isn't correct |
| 8 |
Incorrect |
18 ms |
15360 KB |
Output isn't correct |
| 9 |
Correct |
20 ms |
15352 KB |
Output is correct |
| 10 |
Incorrect |
20 ms |
15656 KB |
Output isn't correct |
| 11 |
Incorrect |
21 ms |
15708 KB |
Output isn't correct |
| 12 |
Correct |
25 ms |
16896 KB |
Output is correct |
| 13 |
Incorrect |
36 ms |
17776 KB |
Output isn't correct |
| 14 |
Correct |
37 ms |
19320 KB |
Output is correct |
| 15 |
Correct |
42 ms |
20344 KB |
Output is correct |
| 16 |
Correct |
83 ms |
26128 KB |
Output is correct |
| 17 |
Execution timed out |
101 ms |
25624 KB |
Time limit exceeded |
| 18 |
Execution timed out |
142 ms |
37748 KB |
Time limit exceeded |
| 19 |
Execution timed out |
142 ms |
37744 KB |
Time limit exceeded |
| 20 |
Execution timed out |
214 ms |
36632 KB |
Time limit exceeded |
