Submission #544794

#TimeUsernameProblemLanguageResultExecution timeMemory
544794rainboyPrinted Circuit Board (CEOI12_circuit)C11
85 / 100
167 ms6012 KiB
#pragma GCC optimize("O3") #include <stdio.h> #include <string.h> #define N 200000 unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } long long cross2(int x1, int y1, int x2, int y2) { return (long long) x1 * y2 - (long long) x2 * y1; } int xx[N], yy[N], ii[N * 2]; long long cross(int i, int j, int k) { return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]); } int cmp(int h1, int h2) { long long c = cross2(xx[ii[h1]], yy[ii[h1]], xx[ii[h2]], yy[ii[h2]]); return c ? (c < 0 ? -1 : 1) : (h1 & 1) - (h2 & 1); } void sort(int *hh, int l, int r) { while (l < r) { int i = l, j = l, k = r, h_ = hh[l + rand_() % (r - l)], tmp; while (j < k) { int c = cmp(hh[j], h_); if (c == 0) j++; else if (c < 0) { tmp = hh[i], hh[i] = hh[j], hh[j] = tmp; i++, j++; } else { k--; tmp = hh[j], hh[j] = hh[k], hh[k] = tmp; } } sort(hh, l, i); l = k; } } int iq[1 + N], pq[N], cnt, x_, y_; double t(int i, int j) { return (double) cross2(xx[i], yy[i], xx[j] - xx[i], yy[j] - yy[i]) / cross2(x_, y_, xx[j] - xx[i], yy[j] - yy[i]); } int lt(int i, int j) { double t1 = t(ii[i << 1 | 0], ii[i << 1 | 1]), t2 = t(ii[j << 1 | 0], ii[j << 1 | 1]); if (t1 != t2) return t1 < t2; return cross(ii[i << 1 | 0], ii[j << 1 | 0], ii[j << 1 | 1]) < 0 || cross(ii[i << 1 | 1], ii[j << 1 | 0], ii[j << 1 | 1]) < 0; } int p2(int p) { return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p); } void pq_up(int i) { int p, q, j; for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_dn(int i) { int p, q, j; for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_add(int i) { pq[i] = ++cnt, pq_up(i); } void pq_remove(int i) { if (pq[i]) { int j = iq[cnt--]; if (j != i) pq[j] = pq[i], pq_up(j), pq_dn(j); pq[i] = 0; } } int main() { static int hh[N * 2]; static char visible[N]; int n, n_, g, h, h_, i; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d%d", &xx[i], &yy[i]); n_ = 0; for (i = 0; i < n; i++) { long long c = cross2(xx[i], yy[i], xx[(i + 1) % n], yy[(i + 1) % n]); if (c < 0) { ii[i << 1 | 0] = i, ii[i << 1 | 1] = (i + 1) % n; hh[n_++] = i << 1 | 0, hh[n_++] = i << 1 | 1; } else if (c > 0) { ii[i << 1 | 0] = (i + 1) % n, ii[i << 1 | 1] = i; hh[n_++] = i << 1 | 0, hh[n_++] = i << 1 | 1; } } sort(hh, 0, n_); memset(visible, 1, n * sizeof *visible); for (h = 0; h < n_; h++) { h_ = hh[h]; x_ = xx[ii[h_]], y_ = yy[ii[h_]]; if ((h_ & 1) == 0) pq_add(h_ >> 1); else pq_remove(h_ >> 1); if (cnt) { i = iq[1]; if (cross(ii[i << 1 | 0], ii[i << 1 | 1], ii[h_]) > 0) visible[ii[h_]] = 0; } } for (h = 0; h < n_; h = h_) { int h1, i_; h1 = hh[h], h_ = h, i_ = -1; while (h_ < n_ && cross2(xx[ii[h1]], yy[ii[h1]], xx[ii[hh[h_]]], yy[ii[hh[h_]]]) == 0) { i = ii[hh[h_++]]; if (i_ == -1 || xx[i_] > xx[i]) i_ = i; } for (g = h; g < h_; g++) { i = ii[hh[g]]; if (i != i_) visible[i] = 0; } } 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:104:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
circuit.c:106:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...