#include<stdio.h>
#include<algorithm>
using namespace std;
struct point {
long long x, y;
int c;
bool operator <(const point &p)const {
return x*p.y != y*p.x ? x*p.y<y*p.x : x<p.x;
}
}w[200001];
struct point2 {
int x, y;
}P[200001];
struct vector2 {
double x, y;
int c;
}w2[200001], t1, t2, t3;
double X1, X2, Y1, Y2, tt;
int r[400001], N, i, c, sz, IT2[600001];
bool v[400001];
double IT[600001], INF = 1e9;
double F(double x, double y) {
tt = (Y2*x - X2*y) / ((X1 - X2)*y - (Y1 - Y2)*x);
return Y1*tt + Y2*(1 - tt);
}
bool ccw() {
return (t2.x - t1.x)*(t3.y - t1.y) - (t2.y - t1.y)*(t3.x - t1.x)<0;
}
void Do(int b, int e, int k) {
int s = b - sz, l = e - sz, t = 1;
double tp;
if (k == 8999) {
k = k;
}
while (b <= e) {
if (b & 1) {
tp = F(w2[s].x, w2[s].y);
if (tp<IT[b])IT[b] = tp, IT2[b] = k;
else if (tp == IT[b]) {
t1.y = tp; t1.x = tp*(double)w2[s].x / w2[s].y;
t2.x = P[IT2[b]].x, t2.y = P[IT2[b]].y;
if (t1.y != P[k].y)t3.x = P[k].x, t3.y = P[k].y;
else t3.x = P[k + 1].x, t3.y = P[k + 1].y;
if (ccw())IT2[b] = k;
}
}
if (!(e & 1)) {
tp = F(w2[l - t + 1].x, w2[l - t + 1].y);
if (tp<IT[e])IT[e] = tp, IT2[e] = i;
else if (tp == IT[e]) {
t1.y = tp; t1.x = tp*(double)w2[l - t + 1].x / w2[l - t + 1].y;
t2.x = P[IT2[e]].x, t2.y = P[IT2[e]].y;
if (t1.y != P[k].y)t3.x = P[k].x, t3.y = P[k].y;
else t3.x = P[k + 1].x, t3.y = P[k + 1].y;
if (ccw())IT2[e] = k;
}
}
if (b & 1)s += t;
if (!(e & 1))l -= t;
t <<= 1;
b = (b + 1) >> 1, e = (e - 1) >> 1;
}
}
void DFS(int s, int z, int a, int b) {
int tt = s;
if (s >= c)return;
if (s == 0) {
if (a >= sz)return;
tt = 1;
}
if (b == -1 && IT[a] != INF)b = IT2[a];
else if (IT[a] != INF) {
X1 = P[b].x, X2 = P[b + 1].x, Y1 = P[b].y, Y2 = P[b + 1].y;
if (F(w2[tt].x, w2[tt].y)>IT[a])b = IT2[a];
}
if (a >= sz) {
if (a - sz >= 1 && a - sz<c)IT2[a] = b;
return;
}
DFS(s, z >> 1, a << 1, b);
DFS(s + z, z >> 1, (a << 1) + 1, b);
}
bool Pos(int a) {
if (abs(a) == N - 1)return true;
return a<0 ? false : a>1 ? false : true;
}
int main()
{
scanf("%d", &N);
for (i = 0; i<N; i++) {
scanf("%d%d", &P[i].x, &P[i].y);
w[i].x = P[i].x, w[i].y = P[i].y, w[i].c = i;
}
P[N] = P[0];
sort(w, w + N);
for (i = 0; i<N; i++) {
c++;
if (i && w[i].x*w[i - 1].y == w[i].y*w[i - 1].x)c--;
else w2[c].x = w[i].x, w2[c].y = w[i].y, w2[c].c = w[i].c;
r[w[i].c] = c;
}
r[N] = r[0];
sz = 1;
while (sz <= c)sz *= 2;
for (i = 1; i<sz * 2; i++)IT[i] = INF;
for (i = 0; i<N; i++) {
if (r[i] == r[i + 1])continue;
X1 = P[i].x, Y1 = P[i].y, X2 = P[i + 1].x, Y2 = P[i + 1].y;
Do(sz + min(r[i], r[i + 1]), sz + max(r[i], r[i + 1]) - 1, i);
}
DFS(0, sz >> 1, 1, -1);
v[w2[1].c] = v[w2[c].c] = true;
for (i = 1; i<c - 1; i++) {
if (Pos(w2[i + 1].c - IT2[sz + i]) || Pos(w2[i + 1].c - IT2[sz + i + 1]))v[w2[i + 1].c] = true;
}
c = 0;
for (i = 0; i<N; i++) {
if (v[i])c++;
}
printf("%d\n", c);
for (i = 0; i<N; i++)if (v[i])printf("%d ", i + 1);
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
circuit.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &P[i].x, &P[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
624 KB |
Output is correct |
| 3 |
Correct |
4 ms |
860 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1004 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1796 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1880 KB |
Output is correct |
| 7 |
Correct |
19 ms |
3164 KB |
Output is correct |
| 8 |
Correct |
8 ms |
3164 KB |
Output is correct |
| 9 |
Correct |
8 ms |
3164 KB |
Output is correct |
| 10 |
Correct |
9 ms |
3164 KB |
Output is correct |
| 11 |
Correct |
10 ms |
3164 KB |
Output is correct |
| 12 |
Correct |
16 ms |
3908 KB |
Output is correct |
| 13 |
Correct |
21 ms |
4888 KB |
Output is correct |
| 14 |
Correct |
24 ms |
6560 KB |
Output is correct |
| 15 |
Correct |
25 ms |
7812 KB |
Output is correct |
| 16 |
Correct |
59 ms |
13520 KB |
Output is correct |
| 17 |
Correct |
89 ms |
14752 KB |
Output is correct |
| 18 |
Execution timed out |
104 ms |
25920 KB |
Time limit exceeded |
| 19 |
Execution timed out |
111 ms |
28396 KB |
Time limit exceeded |
| 20 |
Execution timed out |
160 ms |
31132 KB |
Time limit exceeded |
