Submission #548848

#TimeUsernameProblemLanguageResultExecution timeMemory
548848rainboyPrinted Circuit Board (CEOI12_circuit)C11
85 / 100
34 ms1184 KiB
#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 <= 100000); 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)

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 timeMemoryGrader output
Fetching results...