#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
const int N = 100000;
int xx[N], yy[N], zz[N], xx_[N << 1], yy_[N], ff[N], ww[N], ll[N], rr[N], hh[N], aa0[N], aa1[N];
set<pair<int, int>> ss;
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 cnt = 0;
long long s = 0;
for (int i = 0, j = 0; i < n; s -= zz[i++]) {
while (xx[j] != xx[(j + 1) % n] || s + zz[j] < s_ / 2)
s += zz[j], j = (j + 1) % n;
if (xx[i] == xx[(i + 1) % n])
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 (yy[i] <= y && y <= yy[(i + 1) % n] && yy[(j + 1) % n] <= y && y <= yy[j])
xx_[cnt << 1 ^ 0] = xl + 1, xx_[cnt << 1 ^ 1] = xr, yy_[cnt] = y, cnt++;
} 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 (yy[j] <= y && y <= yy[(j + 1) % n] && yy[(i + 1) % n] <= y && y <= yy[i])
xx_[cnt << 1 ^ 0] = xl + 1, xx_[cnt << 1 ^ 1] = xr, yy_[cnt] = y, cnt++;
}
}
for (int e = 0; e < cnt << 1; e++)
ff[e] = e;
sort(ff, ff + (cnt << 1), [] (int f0, int f1) { return xx_[f0] != xx_[f1] ? xx_[f0] < xx_[f1] : f0 < f1; });
int k = 0;
for (int i = 0; i < n; i++)
if (xx[i] == xx[(i + 1) % n]) {
int l = yy[i], r = yy[(i + 1) % n];
if (l > r)
swap(l, r);
ww[k] = xx[i], ll[k] = l, rr[k] = r, k++;
}
for (int g = 0; g < k; g++)
hh[g] = g;
sort(hh, hh + k, [] (int h0, int h1) { return ww[h0] < ww[h1]; });
int xl_ = -1, xr_ = -1, y_ = -1;
ss.clear();
for (int e = 0, g = 0; e < cnt << 1 || g < k; )
if (e < cnt << 1 && (g == k || xx_[ff[e]] <= ww[hh[g]])) {
int f = ff[e++];
if (f & 1) {
f >>= 1;
if (ss.contains({ yy_[f], f })) {
xl_ = xx_[f << 1 ^ 0] - 1;
xr_ = xx_[f << 1 ^ 1];
y_ = yy_[f];
break;
}
} else {
f >>= 1;
ss.insert({ yy_[f], f });
}
} else {
int h = hh[g++], l = ll[h], r = rr[h];
while (true) {
auto it = ss.upper_bound({ l + 1, -1 });
if (it == ss.end() || (*it).first >= r)
break;
ss.erase(it);
}
}
if (xl_ == -1)
continue;
int il = 0;
while (!contains(il, (il + 1) % n, xl_, y_))
il = (il + 1) % n;
if (yy[il] == yy[(il + 1) % n])
il = (il + 1) % n;
int ir = n - 1;
while (!contains(ir, (ir - 1 + n) % n, xr_, y_))
ir = (ir - 1 + n) % n;
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 (yy[(i + 2) % n] < yy[i])
aa0[k0] ^= 1;
} else {
aa0[k0] = xx[i] - xx[(i + 1) % n] << 1;
if (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 (!contains(il, (il + 1) % n, xr_, y_))
il = (il + 1) % n;
if (yy[il] == yy[(il + 1) % n])
il = (il + 1) % n;
ir = n - 1;
while (!contains(ir, (ir - 1 + n) % n, xl_, y_))
ir = (ir - 1 + n) % n;
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 (yy[(i + 2) % n] < yy[i])
aa1[k1] ^= 1;
} else {
aa1[k1] = xx[i] - xx[(i + 1) % n] << 1;
if (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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |