#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
struct segment {
int x, l, r, pos, dir; ll s, e;
bool operator<(const segment &ot) const {
return l < ot.l;
}
};
bool operator<(const segment &s, const int &y) { return s.l < y; }
bool operator<(const int &y, const segment &s) { return y < s.l; }
int ccw(pii p, pii q, pii r) {
ll x = 1ll * (q.ff - p.ff) * (r.ss - q.ss) - 1ll * (q.ss - p.ss) * (r.ff - q.ff);
return (x > 0) - (x < 0);
}
bool cyclic_shift(vector<int> S, vector<int> T) {
if (S.size() != T.size()) return false;
int n = S.size();
int F[n]{};
for (int i = 1, p = 0; i < n; i++) {
while (p > 0 && S[i] != S[p]) p = F[p - 1];
if (S[i] == S[p]) ++p;
F[i] = p;
}
T.resize(2 * n);
for (int i = 0; i < n; i++) T[n + i] = T[i];
for (int i = 0, p = 0; i < 2 * n; i++) {
while (p > 0 && T[i] != S[p]) p = F[p - 1];
if (T[i] == S[p]) ++p;
if (p == n) return true;
}
return false;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
int n;
cin >> n;
int x[n], y[n], r[n];
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
int minx = x[0], miny = y[0];
for (int i = 1; i < n; i++) {
minx = min(minx, x[i]);
miny = min(miny, y[i]);
}
for (int i = 0; i < n; i++) x[i] -= minx, y[i] -= miny;
ll tot = 0;
for (int i = 0; i < n; i++) tot += abs(x[i] - x[(i + 1) % n]) + abs(y[i] - y[(i + 1) % n]);
for (int dir = 0; dir < 2; dir++) {
for (int i = 0; i < n; i++) {
pii prv = {x[(i + n - 1) % n], y[(i + n - 1) % n]};
pii cur = {x[i], y[i]};
pii nxt = {x[(i + 1) % n], y[(i + 1) % n]};
r[i] = ccw(prv, cur, nxt);
}
int det = accumulate(r, r + n, 0);
// for (int i = 0; i < n; i++) cout << r[i] << ' ';
// cout << det << endl;
if (det < 0) {
assert(det == -4);
reverse(x, x + n);
reverse(y, y + n);
reverse(r, r + n);
for (int i = 0; i < n; i++) r[i] *= -1;
}
else assert(det == 4);
ll idx[n]{};
for (int i = 1; i < n; i++) {
idx[i] = idx[i - 1] + abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);
}
// cout << dir << '\n';
set<segment, less<>> ST;
auto cut = [&](int l, int r) {
auto it = ST.lower_bound(l);
if (it != ST.begin()) {
it = prev(it);
segment tmp = *it;
if (tmp.r >= l) {
ST.erase(it);
ll m1 = tmp.dir ? tmp.s + (l - 1 - tmp.l) : tmp.s - (l - 1 - tmp.l);
ll m2 = tmp.dir ? m1 + 1 : m1 - 1;
// m1 = (m1 % tot + tot) % tot;
// m2 = (m2 % tot + tot) % tot;
ST.insert({tmp.x, tmp.l, l - 1, tmp.pos, tmp.dir, tmp.s, m1});
ST.insert({tmp.x, l, tmp.r, tmp.pos, tmp.dir, m2, tmp.e});
}
}
it = ST.upper_bound(r);
if (it != ST.begin()) {
it = prev(it);
segment tmp = *it;
if (tmp.r > r) {
ST.erase(it);
ll m1 = tmp.dir ? tmp.s + (r - tmp.l) : tmp.s - (r - tmp.l);
ll m2 = tmp.dir ? m1 + 1 : m1 - 1;
// m1 = (m1 % tot + tot) % tot;
// m2 = (m2 % tot + tot) % tot;
ST.insert({tmp.x, tmp.l, r, tmp.pos, tmp.dir, tmp.s, m1});
ST.insert({tmp.x, r + 1, tmp.r, tmp.pos, tmp.dir, m2, tmp.e});
}
}
};
vector<segment> S;
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
if (x[i] == x[j]) {
int dir = y[j] > y[i];
int l, rr; ll s, e;
if (dir) {
l = r[i] < 0 ? y[i] : y[i] + 1;
rr = r[j] < 0 ? y[j] : y[j] - 1;
}
else {
l = r[i] < 0 ? y[i] : y[i] - 1;
rr = r[j] < 0 ? y[j] : y[j] + 1;
}
s = r[i] < 0 ? idx[i] : idx[i] + 1;
e = r[j] < 0 ? idx[j] : idx[j] - 1;
if (!dir) {
swap(l, rr);
swap(s, e);
}
if (l <= rr) S.push_back({x[i], l, rr, i, dir, s, e});
// cout << "raw segment x = " << x[i] << ", " << "y = [" << l << ", " << rr << "] , idx = " << s << ", " << e << '\n';
}
}
sort(S.begin(), S.end(), [&](const segment &p, const segment &q) { return p.x < q.x; });
vector<pair<segment, segment>> V;
for (segment &s : S) {
cut(s.l, s.r);
auto it = ST.lower_bound(s.l);
for (; it != ST.end() && it->l <= s.r; it = ST.erase(it)) {
if (s.dir) {
segment prv = *it;
assert(!prv.dir);
segment cur = {s.x, prv.l, prv.r, s.pos, s.dir, 0, 0};
cur.s = s.s + (prv.l - s.l);
cur.e = s.s + (prv.r - s.l);
// cur.s %= tot;
// cur.e %= tot;
V.push_back({prv, cur});
// cout << "two segments at [" << prv.l << ", " << prv.r << "] with x = " << prv.x << ", " << cur.x << "\n";
// cout << "index L : " << prv.s << ", " << prv.e << '\n';
// cout << "index R : " << cur.s << ", " << cur.e << '\n';
}
}
ST.insert(s);
}
for (auto &[L, R] : V) {
ll Y = L.e + L.r + R.l - R.s + tot / 2;
Y = (Y % tot + tot) % tot;
// cout << "two segments at [" << L.l << ", " << L.r << "] with x = " << L.x << ", " << R.x << "\n";
// cout << "at Y = " << Y << '\n';
if (Y % 2 != 0) continue;
Y /= 2;
if (max(L.l, R.l) <= Y && Y <= min(L.r, R.r)) {
vector<int> S, T;
{
if (Y != y[R.pos]) {
S.push_back(r[R.pos] > 0 ? -1 : -2);
S.push_back(Y - y[R.pos]);
S.push_back(-1);
}
S.push_back(R.x - L.x);
if (Y != y[(L.pos + 1) % n]) {
S.push_back(-1);
S.push_back(Y - y[(L.pos + 1) % n]);
S.push_back(r[(L.pos + 1) % n] > 0 ? -1 : -2);
}
for (int v = (L.pos + 1) % n; ; v = (v + 1) % n) {
S.push_back(abs(x[v] - x[(v + 1) % n]) + abs(y[v] - y[(v + 1) % n]));
if ((v + 1) % n == R.pos) {
break;
}
S.push_back(r[(v + 1) % n] > 0 ? -1 : -2);
}
int pos = 0;
while (S[pos] > 0) ++pos;
rotate(S.begin(), S.begin() + pos, S.end());
vector<int> V;
for (int x : S) {
if (V.empty() || V.back() < 0 || x < 0) V.push_back(x);
else V.back() += x;
}
S = V;
}
{
if (Y != y[L.pos]) {
T.push_back(r[L.pos] > 0 ? -1 : -2);
T.push_back(y[L.pos] - Y);
T.push_back(-1);
}
T.push_back(R.x - L.x);
if (Y != y[(R.pos + 1) % n]) {
T.push_back(-1);
T.push_back(y[(R.pos + 1) % n] - Y);
T.push_back(r[(R.pos + 1) % n] > 0 ? -1 : -2);
}
for (int v = (R.pos + 1) % n; ; v = (v + 1) % n) {
T.push_back(abs(x[v] - x[(v + 1) % n]) + abs(y[v] - y[(v + 1) % n]));
if ((v + 1) % n == L.pos) {
break;
}
T.push_back(r[(v + 1) % n] > 0 ? -1 : -2);
}
int pos = 0;
while (T[pos] > 0) ++pos;
rotate(T.begin(), T.begin() + pos, T.end());
vector<int> V;
for (int x : T) {
if (V.empty() || V.back() < 0 || x < 0) V.push_back(x);
else V.back() += x;
}
T = V;
}
// cout << "string S = [ ";
// for (int x : S) cout << x << ' '; cout << "]\n";
// cout << "string T = [ ";
// for (int x : T) cout << x << ' '; cout << "]\n";
bool flag = cyclic_shift(S, T);
if (!flag) {
reverse(S.begin(), S.end());
flag = cyclic_shift(S, T);
}
if (flag) {
if (!dir) {
cout << L.x + minx << ' ' << Y + miny << ' ' << R.x + minx << ' ' << Y + miny << '\n';
}
else {
cout << Y + miny << ' ' << L.x + minx << ' ' << Y + miny << ' ' << R.x + minx << '\n';
}
return 0;
}
}
}
for (int i = 0; i < n; i++) swap(x[i], y[i]);
}
cout << "NO\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
