#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
ll tot_area; // check that its even
pii operator*(int a, pii b) {
return pii(b.first*a, b.second*a);
}
pii operator*(pii b, int a) {
return pii(b.first*a, b.second*a);
}
pii operator+(pii a, pii b) {
return pii(a.first+b.first, a.second+b.second);
}
ll operator*(pii a, pii b) {
return (ll)a.first*b.second-(ll)a.second*b.first;
}
class poly;
bool cong(poly *a, poly *b);
typedef pair<poly*, poly*> ppp;
ppp merge(ppp a, ppp b, int t);
void pq_push(poly *a);
class poly {
public:
pii pt1, pt2;
pii normal;
ll area = 0; // only for compressed
bool dead = 0;
int length;
int turn; // 0 -> ccw, 1 -> cw, 2->straight
poly *l = nullptr;
poly *r = nullptr;
ppp compressed = ppp(nullptr, nullptr); // actual polygon on this edge, head and tail
poly(pii pt1, pii pt2, int turn, poly *l = nullptr, poly *r = nullptr, bool make_compress = 0) : pt1(pt1), pt2(pt2), l(l), r(r), turn(turn) {
if (pt2.first > pt1.first) normal = pii(0, 1);
if (pt2.second > pt1.second) normal = pii(-1, 0);
if (pt2.first < pt1.first) normal = pii(0, -1);
if (pt2.second < pt1.second) normal = pii(1, 0);
length = abs(pt1.first-pt2.first)+abs(pt1.second-pt2.second);
if (make_compress) {
poly *np = new poly(pt1, pt2, 0);
compressed = ppp(np, np);
}
}
bool blocked() {
return 0;
}
void fuse_next() {
r->dead = 1;
pt2 = r->pt2;
length += r->length;
turn = r->turn;
if (r->r != nullptr) r->r->l = this;
r = r->r;
}
void fuse_prev() {
l->dead = 1;
pt1 = l->pt1;
length += l->length;
if (l->l != nullptr) l->l->r = this;
l = l->l;
}
void del() {
dead = 1;
if (l->turn != turn) {
l->r = r;
r->l = l;
l->turn = 2;
}
else {
assert(l->turn == 0 & turn == 0);
if (l->length < r->length) {
l->dead = 1;
r->compressed = merge(l->compressed, r->compressed, 0);
assert(l->l->turn == 1);
l->l->turn = 0;
l->l->r = r;
r->l = l->l;
r->length -= l->length;
r->pt1 = l->pt1;
}
else {
r->dead = 1;
l->compressed = merge(l->compressed, r->compressed, 0);
assert(r->turn == 1);
l->turn = 0;
l->r = r->r;
r->r->l = l;
l->length -= r->length;
l->pt2 = r->pt2;
}
}
}
void straighten() {
if (l->turn == 2) {
compressed = merge(l->compressed, compressed, 2);
fuse_prev();
}
if (turn == 2) {
compressed = merge(compressed, r->compressed, 2);
fuse_next();
}
pq_push(this);
}
void move(int d) {
pii npt1 = pt1+normal*d;
pii npt2 = pt2+normal*d;
compressed.first = new poly(npt1, pt1, 0, nullptr, compressed.first);
compressed.first->area = compressed.first->r->area;
compressed.first->r->l = compressed.first;
compressed.second = new poly(pt2, npt2, 1, compressed.second, nullptr);
compressed.second->l->r = compressed.second;
compressed.second->l->turn = 0;
compressed.first->area += (ll) d*length;
l->length -= d;
r->length -= d;
pt1 = npt1;
pt2 = npt2;
if (l->length == 0) l->del();
if (r->length == 0) r->del();
}
bool compress() { // l is defined, r is defined, l->turn = turn = 0, no opposite direction edge "jutting out"
// return 0 if nothing happens, return 1 if you find that this orientation has no equiareal, and exit if you find one
int c_dist = min(l->length, r->length);
ll ex_ar = (ll) c_dist*length;
ll cur_ar = compressed.first->area;
if (2*(cur_ar+ex_ar) >= tot_area) {
ll req_ar = tot_area/2;
if ((req_ar-cur_ar) % length != 0) return 1;
move((req_ar-cur_ar)/length);
compressed.second->turn = 0;
compressed.second->r = new poly(pt2, pt1, 0, compressed.second, compressed.first);
if (cong(this, compressed.first)) {
cout << pt1.first << " " << pt1.second << " " << pt2.first << " " << pt2.second << "\n";
exit(0);
}
return 1;
}
move(c_dist);
straighten();
return 0;
}
};
class pq_node {
public:
poly *rep;
pii pt1;
pii pt2;
int length;
pq_node(poly *r) : rep(r) {
pt1 = r->pt1;
pt2 = r->pt2;
length = r->length;
}
};
bool operator<(pq_node a, pq_node b) {
return (a.length == b.length) ? (a.rep < b.rep) : (a.length > b.length);
}
priority_queue<pq_node> pq;
void pq_push(poly *a) {
pq.push(pq_node(a));
}
ppp merge(ppp a, ppp b, int t) {
a.first->area += b.first->area;
a.second->r = b.first;
b.first->l = a.second;
a.second->turn = t;
if (t == 2) {
a.second->fuse_next();
}
return ppp(a.first, b.second);
}
bool cong(poly *a, poly *b) {
return 1;
}
const int MAXN = 1e5;
pii points[MAXN];
poly *lines[MAXN];
int n;
void solve(bool orient) {
priority_queue<pq_node>().swap(pq);
for (int i = 0; i < n; i++) lines[i] = new poly(points[i], points[(i+1)%n], 0, nullptr, nullptr, 1);
for (int i = 0; i < n; i++) {
int j = (i+1)%n;
lines[i]->turn = (lines[i]->normal*lines[j]->normal < 0);
lines[i]->r = lines[j];
lines[j]->l = lines[i];
}
for (int i = 0; i < n; i++)
if (abs(lines[i]->normal.first) == orient && lines[i]->turn == 0 && lines[i]->l->turn == 0)
pq_push(lines[i]);
while (!pq.empty()) {
pq_node pn = pq.top();
pq.pop();
if (pn.pt1 != pn.rep->pt1 || pn.pt2 != pn.rep->pt2 || pn.rep->dead) continue;
if (pn.rep->compress()) return;
}
assert(false);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> points[i].first >> points[i].second;
}
tot_area = 0;
for (int i = 0; i < n; i++) {
tot_area += points[i]*points[(i+1)%n];
}
if (tot_area < 0) {
for (int i = 0; i < n/2; i++) swap(points[i], points[n-1-i]);
tot_area = -tot_area;
}
assert(tot_area % 2 == 0); tot_area /= 2;
if (tot_area % 2 == 1) {
cout << "NO\n";
return 0;
}
solve(0);
solve(1);
cout << "NO\n";
}
Compilation message
demarcation.cpp: In constructor 'poly::poly(pii, pii, int, poly*, poly*, bool)':
demarcation.cpp:37:8: warning: 'poly::r' will be initialized after [-Wreorder]
37 | poly *r = nullptr;
| ^
demarcation.cpp:35:6: warning: 'int poly::turn' [-Wreorder]
35 | int turn; // 0 -> ccw, 1 -> cw, 2->straight
| ^~~~
demarcation.cpp:39:2: warning: when initialized here [-Wreorder]
39 | poly(pii pt1, pii pt2, int turn, poly *l = nullptr, poly *r = nullptr, bool make_compress = 0) : pt1(pt1), pt2(pt2), l(l), r(r), turn(turn) {
| ^~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from demarcation.cpp:1:
demarcation.cpp: In member function 'void poly::del()':
demarcation.cpp:76:19: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
76 | assert(l->turn == 0 & turn == 0);
| ~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6996 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6868 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
