# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
548844 | rainboy | Printed Circuit Board (CEOI12_circuit) | C11 | 65 ms | 4952 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#define N 100000
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);
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |