#include <assert.h>
#include <stdio.h>
#define N 200000
long long cross(int x1, int y1, int x2, int y2) {
return (long long) x1 * y2 - (long long) x2 * y1;
}
int xx[N], yy[N], n;
long long cross2(int i, int j) {
i %= n, j %= n;
return cross(xx[i], yy[i], xx[j], yy[j]);
}
long long cross3(int i, int j, int k) {
i %= n, j %= n, k %= n;
return cross(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}
int compare(int i, int j) {
int i0 = i, i1 = i + 1, j0 = j, j1 = j + 1, tmp;
long long c0, c1;
if (cross2(i0, i1) > 0)
tmp = i0, i0 = i1, i1 = tmp;
if (cross2(j0, j1) > 0)
tmp = j0, j0 = j1, j1 = tmp;
c0 = cross3(i0, i1, j0), c1 = cross3(i0, i1, j1);
if (c0 >= 0 && c1 >= 0)
return -1;
if (c0 <= 0 && c1 <= 0)
return 1;
c0 = cross3(j0, j1, i0), c1 = cross3(j0, j1, i1);
if (c0 >= 0 && c1 >= 0)
return 1;
if (c0 <= 0 && c1 <= 0)
return -1;
return 0;
}
int main() {
static int ii1[N], jj1[N], ii2[N], jj2[N];
static char visible[N];
int h, i, j, l, cnt1, cnt2, cnt;
scanf("%d", &n);
assert(n <= 190000);
l = -1;
for (i = 0; i < n; i++) {
scanf("%d%d", &xx[i], &yy[i]);
if (l == -1 || cross2(l, i) > 0)
l = i;
}
i = l;
cnt1 = cnt2 = 0;
for (j = l; j < l + n; j++) {
long long c = cross2(j, j + 1);
if (c == 0) {
if (cross2(i, j) == 0 && xx[i % n] > xx[(j + 1) % n])
i = j + 1;
} else if (c < 0) {
if (cross2(j, i) <= 0 && cross2(i, j + 1) < 0)
while (1) {
if (cnt2 == 0) {
ii1[cnt1] = i, jj1[cnt1] = j, cnt1++;
i = j + 1;
break;
}
if (compare(jj2[cnt2 - 1], j) <= 0)
break;
if (cross2(j + 1, ii2[cnt2 - 1]) < 0) {
ii1[cnt1] = i, jj1[cnt1] = j, cnt1++;
i = j + 1;
break;
}
cnt2--;
if (cross3(j, j + 1, ii2[cnt2]) <= 0) {
ii1[cnt1] = i, jj1[cnt1] = j, cnt1++;
i = ii2[cnt2];
break;
}
}
} else {
if (cross2(j, i) >= 0 && cross2(i, j + 1) > 0) {
while (1) {
if (cnt1 == 0) {
ii2[cnt2] = i, jj2[cnt2] = j, cnt2++;
i = j + 1;
break;
}
if (compare(jj1[cnt1 - 1], j) <= 0)
break;
if (cross2(j + 1, ii1[cnt1 - 1]) > 0) {
ii2[cnt2] = i, jj2[cnt2] = j, cnt2++;
i = j + 1;
break;
}
cnt1--;
if (cross3(j, j + 1, ii1[cnt1]) >= 0) {
ii2[cnt2] = i, jj2[cnt2] = j, cnt2++;
i = ii1[cnt1];
break;
}
}
}
}
}
visible[i % n] = 1;
for (h = 0; h < cnt1; h++)
visible[ii1[h] % n] = 1;
for (h = 0; h < cnt2; h++)
visible[ii2[h] % n] = 1;
cnt = 0;
for (i = 0; i < n; i++)
if (visible[i])
cnt++;
printf("%d\n", cnt);
for (i = 0; i < n; i++)
if (visible[i])
printf("%d ", i + 1);
printf("\n");
return 0;
}
Compilation message
circuit.c: In function 'main':
circuit.c:48:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
circuit.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Correct |
4 ms |
340 KB |
Output is correct |
| 6 |
Correct |
4 ms |
340 KB |
Output is correct |
| 7 |
Correct |
7 ms |
468 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
3 ms |
340 KB |
Output is correct |
| 10 |
Correct |
3 ms |
340 KB |
Output is correct |
| 11 |
Correct |
5 ms |
364 KB |
Output is correct |
| 12 |
Correct |
4 ms |
468 KB |
Output is correct |
| 13 |
Correct |
9 ms |
524 KB |
Output is correct |
| 14 |
Correct |
9 ms |
548 KB |
Output is correct |
| 15 |
Correct |
13 ms |
644 KB |
Output is correct |
| 16 |
Correct |
24 ms |
1064 KB |
Output is correct |
| 17 |
Correct |
31 ms |
1096 KB |
Output is correct |
| 18 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 19 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 20 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
