#include <bits/stdc++.h>
using namespace std;
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 2e5 + 2;
const ll INF = 2e9 + 2;
struct Pt{
ll x, y, ind;
Pt(const ll &x_ = 0, const ll &y_ = 0, const ll &ind_ = 0) : x(x_), y(y_), ind(ind_) {}
friend bool operator< (const Pt &p, const Pt &q) {
return p.ind != q.ind && (p.x < q.x || (p.x == q.x && p.y < q.y));
}
friend bool operator== (const Pt &p, const Pt &q) {
return p.ind == q.ind;
}
friend std::istream &operator>>(std::istream &is, Pt &p) {
return is >> p.x >> p.y;
}
friend std::ostream &operator<<(std::ostream &os, const Pt &p) {
return os << "(" << p.x << ", " << p.y << ")";
}
};
ll peri = 0, n;
set<pair<ll, ll>> view; // y, poly ind
set<ll> up_is_out; // for which y, in current view, above which is out of the polygon
vector<Pt> poly;
vector<ll> pre_dist;
void clockwise(vector<Pt> &poly, ll n) {
ll lm = -1;
for (int i = 0; i < n; i++) {
if (lm == -1 || poly[i] < poly[lm]) lm = i;
}
if (poly[(lm + 1) % n].y != poly[lm].y) reverse(poly.begin(), poly.end());
vector<Pt> temp = poly;
poly.clear();
for (int i = n - 1 - lm; i < n; i++) poly.push_back(temp[i]);
for (int i = 0; i < n - 1 - lm; i++) poly.push_back(temp[i]);
}
vector<Pt> transform(vector<Pt> poly, ll n, ll swap_xy, ll mx, ll my) {
if (swap_xy) {
for (int i = 0; i < n; i++) {
swap(poly[i].x, poly[i].y);
}
}
for (int i = 0; i < n; i++) {
poly[i].x *= mx, poly[i].y *= my;
}
clockwise(poly, n);
return poly;
}
ll find_d(int a, int b) {
if (a < b) return pre_dist[b - 1] - (a ? pre_dist[a - 1] : 0);
return pre_dist[n - 1] - pre_dist[a - 1] + (b ? pre_dist[b - 1] : 0);
}
int find_h(int ind) {
ll h = (ind + 1) % n; // hrizontal neighbour
if (poly[h].x == poly[ind].x) h = (n + ind - 1) % n;
return h;
}
void comp_pre_dist() {
pre_dist[0] = abs(poly[0].x - poly[1].x) + abs(poly[0].y - poly[1].y);
for (int i = 1; i < n; i++) {
pre_dist[i] = pre_dist[i - 1] + abs(poly[i].x - poly[(i + 1) % n].x) + abs(poly[i].y - poly[(i + 1) % n].y);
}
}
void add(Pt &p){
ll h = find_h(p.ind);
if (poly[h].x < p.x) {
view.erase(make_pair(p.y, h));
up_is_out.erase(p.y);
} else {
view.insert(make_pair(p.y, p.ind));
auto it = view.find(make_pair(p.y, p.ind));
if (it == view.begin()) return;
it--;
if (up_is_out.find((*it).first) == up_is_out.end()) up_is_out.insert(p.y);
}
}
bool precheck(ll &a, ll &b, ll &needed) {
ll excess = peri - find_d(a, b) - abs(poly[a].x - poly[b].x), h_x, changed = 0;
if (excess < 0 || (excess % 2)) return false;
excess /= 2;
needed = max(poly[a].x, poly[b].x) + excess;
h_x = poly[find_h(a)].x;
if (h_x < needed) return false;
else if (h_x == needed) a = find_h(a), changed++;
h_x = poly[find_h(b)].x;
if (h_x < needed) return false;
else if (h_x == needed) b = find_h(b), changed++;
return true;
}
bool compare(vector<Pt> p1, vector<Pt> p2) {
sort(p1.begin(), p1.end());
vector<Pt> poly;
for (int i = 0; i < 2; i++) {
for (int j = -1; j < 2; j += 2) {
for (int k = -1; k < 2; k += 2) {
poly = transform(p2, p2.size(), i, j, k);
sort(poly.begin(), poly.end());
ll x_d = INF, y_d = INF, flag = 1;
for (int it = 0; it < p1.size(); it++) {
if (x_d == INF) x_d = p1[it].x - poly[it].x;
else if (x_d != p1[it].x - poly[it].x) flag = 0;
if (y_d == INF) y_d = p1[it].y - poly[it].y;
else if (y_d != p1[it].y - poly[it].y) flag = 0;
}
if (flag) return 1;
}
}
}
return 0;
}
bool check(ll &a, ll &b, ll &x, ll &y1, ll &y2) {
vector<Pt> p1, p2;
ll needed;
y1 = poly[b].y;
y2 = poly[a].y;
if (precheck(a, b, needed)) {
x = needed;
if (a < b) {
for (int i = a + 1; i < b; i++) p1.push_back(poly[i]);
for (int i = 0; i < a; i++) p2.push_back(poly[i]);
for (int i = b + 1; i < n; i++) p2.push_back(poly[i]);
} else {
for (int i = a + 1; i < n; i++) p1.push_back(poly[i]);
for (int i = 0; i < b; i++) p1.push_back(poly[i]);
for (int i = b + 1; i < a; i++) p2.push_back(poly[i]);
}
if (poly[b].x != x) {
p1.push_back(poly[b]);
p1.push_back(Pt(x, y1, n + 2));
} else if (p1.size() && p1.back().x != x) p1.push_back(Pt(x, y1, n + 2));
if (poly[a].x != x) {
p1.push_back(poly[a]);
p1.push_back(Pt(x, y2, n + 1));
} else if (p1.size() && p1.front().x != x) p1.push_back(Pt(x, y2, n + 1));
p2.push_back(Pt(x, y1, n + 1));
p2.push_back(Pt(x, y2, n + 2));
if (p1.size() == p2.size() && compare(p1, p2)) return true;
}
return false;
}
bool check_vertical(ll &x, ll &y1, ll &y2) {
for (int i = 0; i < n; i++) poly[i].ind = i;
view.clear();
up_is_out.clear();
pre_dist.resize(n);
vector<Pt> pts;
for (int i = 0; i < n; i++) pts.push_back(poly[i]);
sort(pts.begin(), pts.end());
comp_pre_dist();
for (int i = 0; i < n; i += 2) {
add(pts[i]);
add(pts[i + 1]);
ll a, b;
auto it = lower_bound(view.begin(), view.end(), make_pair(pts[i].y, pts[i].ind));
if (it != view.begin() && it != view.end()) {
a = (*it).second;
b = (*(--it)).second;
if (up_is_out.find((*it).first) == up_is_out.end()
&& check(a, b, x, y1, y2)) return true;
}
it = lower_bound(view.begin(), view.end(), make_pair(pts[i + 1].y, pts[i + 1].ind));
if (it != view.begin() && it != view.end()) {
a = (*it).second;
b = (*(--it)).second;
if (up_is_out.find((*it).first) == up_is_out.end()
&& check(a, b, x, y1, y2)) return true;
}
it = lower_bound(view.begin(), view.end(), make_pair(pts[i + 1].y, pts[i + 1].ind));
if (it != view.end()) it++;
if (it != view.begin() && it != view.end()) {
a = (*it).second;
b = (*(--it)).second;
if (up_is_out.find((*it).first) == up_is_out.end()
&& check(a, b, x, y1, y2)) return true;
}
}
return false;
}
void solve() {
ll x, y1, y2;
cin >> n;
Pt p;
for (int i = 0; i < n; i++) {
cin >> p;
p.ind = i;
poly.push_back(p);
}
for (int i = 0; i < n; i++) {
peri += abs(poly[i].x - poly[(i + 1) % n].x);
peri += abs(poly[i].y - poly[(i + 1) % n].y);
}
peri /= 2;
clockwise(poly, n);
if (check_vertical(x, y1, y2)) {
cout << x << " " << y1 << " " << x << " " << y2 << "\n";
} else {
poly = transform(poly, n, 1, 1, 1);
if (check_vertical(x, y1, y2)) {
if (y1 > y2) swap(y1, y2);
cout << y1 << " " << x << " " << y2 << " " << x << "\n";
} else cout << "NO\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
t = 1;
// cin >> t;
while(t--) {
solve();
}
return 0;
}
Compilation message
demarcation.cpp: In function 'bool compare(std::vector<Pt>, std::vector<Pt>)':
demarcation.cpp:113:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int it = 0; it < p1.size(); it++) {
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
1596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
