Submission #1232610

#TimeUsernameProblemLanguageResultExecution timeMemory
1232610kaiboyDemarcation (BOI14_demarcation)C++20
50 / 100
13 ms3144 KiB
#include <algorithm> #include <iostream> using namespace std; const int N = 200000; int xx[N], yy[N], zz[N], aa0[N], aa1[N]; bool contains(int il, int ir, int x, int y) { int xl = xx[il], yl = yy[il], xr = xx[ir], yr = yy[ir]; if (yl == yr) swap(x, y), swap(xl, yl), swap(xr, yr); return x == xl && (yl < yr ? yl <= y && y < yr : yl >= y && y > yr); } bool check(int *aa, int *bb, int n) { static int cc[N * 3], zz[N * 3]; int m = 0; for (int i = 0; i < n; i++) cc[m++] = aa[i]; for (int i = 0; i < n; i++) cc[m++] = bb[i]; for (int i = 0; i < n; i++) cc[m++] = bb[i]; for (int l = 0, r = 0, i = 1; i < m; i++) if (i + zz[i - l] < r) zz[i] = zz[i - l]; else { r = max(r, l = i); while (r < m && cc[r] == cc[r - l]) r++; zz[i] = r - l; } for (int i = n; i < m; i++) if (zz[i] >= n) return true; return false; } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n; cin >> n; for (int i = 0; i < n; i++) cin >> xx[i] >> yy[i]; for (int flip = 1; flip >= 0; flip--) { for (int i = 0; i < n; i++) swap(xx[i], yy[i]); int i_ = 0; for (int i = 1; i < n; i++) if (yy[i_] > yy[i] || yy[i_] == yy[i] && xx[i_] < xx[i]) i_ = i; for (int i = 0; i < n; i++) zz[i] = xx[(i_ + i) % n]; for (int i = 0; i < n; i++) xx[i] = zz[i]; for (int i = 0; i < n; i++) zz[i] = yy[(i_ + i) % n]; for (int i = 0; i < n; i++) yy[i] = zz[i]; if (yy[0] != yy[1]) { reverse(xx + 1, xx + n); reverse(yy + 1, yy + n); } long long s_ = 0; for (int i = 0; i < n; i++) { int j = (i + 1) % n; s_ += zz[i] = abs(xx[j] - xx[i]) + abs(yy[j] - yy[i]); } if (s_ % 2) { cout << "NO\n"; return 0; } int xl_ = -1, xr_ = -1, y_ = -1; long long s = 0; for (int i = 0, j = 0; i < n; s -= zz[i++]) { while (j % 2 == 0 || s + zz[j] < s_ / 2) s += zz[j], j = (j + 1) % n; if (i % 2) if (yy[i] < yy[(i + 1) % n]) { if (yy[j] < yy[(j + 1) % n]) continue; int xl = xx[i], xr = xx[j]; if (xl > xr) continue; int yl = yy[i], yr = yy[j] - s_ / 2 + s; if (yl > yr || (yr - yl) % 2) continue; int y = (yl + yr) / 2; if (y <= yy[(i + 1) % n] && y >= yy[(j + 1) % n] && (y_ == -1 || xr_ - xl_ > xr - xl)) xl_ = xl, xr_ = xr, y_ = y; } else { if (yy[j] > yy[(j + 1) % n]) continue; int xl = xx[j], xr = xx[i]; if (xl > xr) continue; int yl = yy[j] + s_ / 2 - s, yr = yy[i]; if (yl > yr || (yr - yl) % 2) continue; int y = (yl + yr) / 2; if (y <= yy[(j + 1) % n] && y >= yy[(i + 1) % n] && (y_ == -1 || xr_ - xl_ > xr - xl)) xl_ = xl, xr_ = xr, y_ = y; } } if (y_ == -1) continue; bool bad = false; for (int i = 0; i < n; i++) if (xx[i] == xx[(i + 1) % n] && xl_ < xx[i] && xx[i] < xr_) { int yl = yy[i], yr = yy[(i + 1) % n]; if (yl > yr) swap(yl, yr); if (yl < y_ && y_ < yr) { bad = true; break; } } if (bad) continue; int il = 0; while (il < n && !contains(il, (il + 1) % n, xl_, y_)) il++; if (il == n) continue; if (yy[il] == yy[(il + 1) % n]) il = (il + 1) % n; int ir = n - 1; while (ir >= 0 && !contains(ir, (ir - 1 + n) % n, xr_, y_)) ir--; if (ir < 0) continue; if (yy[ir] == yy[(ir - 1 + n) % n]) ir = (ir - 1 + n) % n; int yil = yy[il]; yy[il] = max(yy[il], y_); int yir = yy[ir]; yy[ir] = max(yy[ir], y_); int k0 = 0; for (int i = il; i != ir; i = (i + 1) % n) { if (xx[i] == xx[(i + 1) % n]) { if (yy[i] < yy[(i + 1) % n]) { aa0[k0] = yy[(i + 1) % n] - yy[i] << 1; if ((i + 1) % n == ir || xx[(i + 2) % n] > xx[i]) aa0[k0] ^= 1; } else { aa0[k0] = yy[i] - yy[(i + 1) % n] << 1; if ((i + 1) % n == ir || xx[(i + 2) % n] < xx[i]) aa0[k0] ^= 1; } } else { if (xx[i] < xx[(i + 1) % n]) { aa0[k0] = xx[(i + 1) % n] - xx[i] << 1; if ((i + 1) % n == ir || yy[(i + 2) % n] < yy[i]) aa0[k0] ^= 1; } else { aa0[k0] = xx[i] - xx[(i + 1) % n] << 1; if ((i + 1) % n == ir || yy[(i + 2) % n] > yy[i]) aa0[k0] ^= 1; } } k0++; } aa0[k0++] = xx[ir] - xx[il] << 1 ^ 1; yy[il] = yil; yy[ir] = yir; il = 0; while (il < n && !contains(il, (il + 1) % n, xr_, y_)) il++; if (il == n) continue; if (yy[il] == yy[(il + 1) % n]) il = (il + 1) % n; ir = n - 1; while (ir >= 0 && !contains(ir, (ir - 1 + n) % n, xl_, y_)) ir--; if (ir < 0) continue; if (yy[ir] == yy[(ir - 1 + n) % n]) ir = (ir - 1 + n) % n; yil = yy[il]; yy[il] = min(yy[il], y_); yir = yy[ir]; yy[ir] = min(yy[ir], y_); int k1 = 0; for (int i = il; i != ir; i = (i + 1) % n) { if (xx[i] == xx[(i + 1) % n]) { if (yy[i] < yy[(i + 1) % n]) { aa1[k1] = yy[(i + 1) % n] - yy[i] << 1; if ((i + 1) % n == ir || xx[(i + 2) % n] > xx[i]) aa1[k1] ^= 1; } else { aa1[k1] = yy[i] - yy[(i + 1) % n] << 1; if ((i + 1) % n == ir || xx[(i + 2) % n] < xx[i]) aa1[k1] ^= 1; } } else { if (xx[i] < xx[(i + 1) % n]) { aa1[k1] = xx[(i + 1) % n] - xx[i] << 1; if ((i + 1) % n == ir || yy[(i + 2) % n] < yy[i]) aa1[k1] ^= 1; } else { aa1[k1] = xx[i] - xx[(i + 1) % n] << 1; if ((i + 1) % n == ir || yy[(i + 2) % n] > yy[i]) aa1[k1] ^= 1; } } k1++; } aa1[k1++] = xx[il] - xx[ir] << 1 ^ 1; yy[il] = yil; yy[ir] = yir; if (k0 != k1) continue; if (check(aa0, aa1, k0)) { if (!flip) cout << xl_ << ' ' << y_ << ' ' << xr_ << ' ' << y_ << '\n'; else cout << y_ << ' ' << xl_ << ' ' << y_ << ' ' << xr_ << '\n'; return 0; } reverse(aa1, aa1 + k1); int a = aa1[0] & 1; for (int h = 0; h + 1 < k1; h++) aa1[h] = aa1[h] & ~1 ^ aa1[h + 1] & 1; aa1[k1 - 1] = aa1[k1 - 1] & ~1 ^ a; if (check(aa0, aa1, k0)) { if (!flip) cout << xl_ << ' ' << y_ << ' ' << xr_ << ' ' << y_ << '\n'; else cout << y_ << ' ' << xl_ << ' ' << y_ << ' ' << xr_ << '\n'; return 0; } } cout << "NO\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...