#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define int long long #define F first #define S second #define SZ(x) ((int)(x).size()) #define ALL(x) x.begin(), x.end() using namespace std; using namespace __gnu_pbds; using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vvi = vector<vi>; using vvl = vector<vl>; using pii = pair<int, int>; using pll = pair<ll, ll>; using vii = vector<pii>; using vll = vector<pll>; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int inf = 0x3f3f3f3f; ll sgn(ll x) { return (x > 0) - (x < 0); } /* struct BIT { int n; vector<int> b; BIT(int _n): n(_n), b(n + 1) {} void upd(int x, int v) { for (; x <= n; x += x & -x) { b[x] += v; } } int qq(int x) { int res = 0; for (; x > 0; x &= x - 1) { res += b[x]; } return res; } }; */ ll calc_area(const vii& a) { ll tot_area = 0; int n = SZ(a); for (int i = 0; i < n; i++) { tot_area += 1ll * a[i].F * a[(i + 1) % n].S - 1ll * a[i].S * a[(i + 1) % n].F; } return abs(tot_area) / 2; } void rotate(vii& a) { int n = SZ(a); for (int i = 0; i < n; i++) { a[i] = {-a[i].S, a[i].F}; } } void flip(vii& a) { int n = SZ(a); for (int i = 0; i < n; i++) { a[i].F = -a[i].F; } } array<int, 3> check(const vii& a, ll tot_area) { int n = SZ(a); // coordinate compression vi d_x, d_y; for (int i = 0; i < n; i++) { d_x.push_back(a[i].F); d_y.push_back(a[i].S); } sort(ALL(d_y)); d_y.erase(unique(ALL(d_y)), d_y.end()); int y_cnt = SZ(d_y); vector<vii> events(y_cnt); ordered_set<int> x_st; for (int i = 0; i < n; i++) { if (a[i].S == a[(i + 1) % n].S) { int y = lower_bound(ALL(d_y), a[i].S) - d_y.begin(); auto [l_x, r_x] = minmax(a[i].F, a[(i + 1) % n].F); events[y].push_back({l_x, r_x}); } } ll now_area = 0; ll cur = 0; int y_cut = -1; auto flip_st = [&](int x) -> void { auto it = x_st.find(x); if (it != x_st.end()) x_st.erase(it); else x_st.insert(x); }; for (int y = 0; y < y_cnt; y++) { for (auto [l_x, r_x]: events[y]) { if (x_st.order_of_key(l_x + 1) & 1) { cur -= r_x - l_x; } else { cur += r_x - l_x; } flip_st(l_x); flip_st(r_x); } int cur_y = d_y[y]; int nxt_y = (y + 1 < y_cnt ? d_y[y + 1] : inf); if (now_area == tot_area / 2 || now_area + cur * (nxt_y - cur_y) > tot_area / 2) { if ((tot_area / 2 - now_area) % cur == 0) { y_cut = d_y[y] + (tot_area / 2 - now_area) / cur; } break; } else { now_area += cur * (nxt_y - cur_y); } } vii upper, lower; if (y_cut == -1) return {-1, -1, -1}; vi x_intersections; for (int i = 0; i < n; i++) { if (a[i].F == a[(i + 1) % n].F) { int x = a[i].F; auto [l_y, r_y] = minmax(a[i].S, a[(i + 1) % n].S); if (l_y < y_cut && y_cut < r_y) { // extra points upper.push_back({x, y_cut}); lower.push_back({x, y_cut}); // standard upper.push_back({x, r_y}); lower.push_back({x, l_y}); // x_intersection x_intersections.push_back(x); x_intersections.push_back(x); } if (y_cut >= r_y) { lower.push_back({x, l_y}); lower.push_back({x, r_y}); } if (y_cut <= l_y) { upper.push_back({x, l_y}); upper.push_back({x, r_y}); } } else { int y = a[i].S; if (y == y_cut && sgn(a[(i + n - 1) % n].S - y_cut) * sgn(a[(i + 2) % n].S - y_cut) < 0) { x_intersections.push_back(a[i].F); x_intersections.push_back(a[(i + 1)].F); } } } // rotate + flip lower bool congruent = 0; sort(ALL(upper)); upper.erase(unique(ALL(upper)), upper.end()); for (int i = SZ(upper) - 1; i >= 0; i--) { upper[i] = {upper[i].F - upper[0].F, upper[i].S - upper[0].S}; } for (int t1 = 0; t1 < 2; t1++) { for (int t2 = 0; t2 < 4; t2++) { vii lower2 = lower; sort(ALL(lower2)); lower2.erase(unique(ALL(lower2)), lower2.end()); for (int i = SZ(lower2) - 1; i >= 0; i--) { lower2[i] = {lower2[i].F - lower2[0].F, lower2[i].S - lower2[0].S}; } congruent |= (upper == lower2); rotate(lower); } flip(lower); } if (congruent && SZ(x_intersections) == 4) { sort(ALL(x_intersections)); int ans_x_l = x_intersections[1], ans_x_r = x_intersections[2]; return {y_cut, ans_x_l, ans_x_r}; } else { return {-1, -1, -1}; } } void sol() { int n; cin >> n; vii a(n); for (int i = 0; i < n; i++) cin >> a[i].F >> a[i].S; // calculate total_area ll tot_area = calc_area(a); cerr << "tot_area = " << tot_area << '\n'; if (tot_area & 1) { cout << "NO\n"; return; } array<int, 3> result = check(a, tot_area); if (result[0] != -1) { cout << result[1] << ' ' << result[0] << ' ' << result[2] << ' ' << result[0] << '\n'; return; } for (int i = 0; i < n; i++) { swap(a[i].F, a[i].S); } result = check(a, tot_area); if (result[0] != -1) { cout << result[0] << ' ' << result[1] << ' ' << result[0] << ' ' << result[2] << '\n'; return; } cout << "NO\n"; } signed main() { cin.tie(nullptr)->sync_with_stdio(false); sol(); }