#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_y;
for (int i = 0; i < n; i++) {
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);
};
// sweep line
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 + cur * (nxt_y - cur_y) > tot_area / 2) {
if ((tot_area / 2 - now_area) % cur == 0) {
y_cut = cur_y + (tot_area / 2 - now_area) / cur;
}
break;
} else {
now_area += cur * (nxt_y - cur_y);
}
}
if (y_cut == -1) return {-1, -1, -1};
vii upper, lower;
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 created by the cut
upper.push_back({x, y_cut});
lower.push_back({x, y_cut});
// normal
upper.push_back({x, r_y});
lower.push_back({x, l_y});
// treat it as two separate edges
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;
/* filter out horizontal lines whose two endpoints extend (vertically) in the same direction */
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) % n].F);
}
}
}
// rotate + flip lower
bool congruent = 0;
sort(ALL(upper));
for (int i = SZ(upper) - 1; i >= 0; i--) {
upper[i] = {upper[i].F - upper[0].F, upper[i].S - upper[0].S};
}
// try all combinations
for (int t1 = 0; t1 < 2; t1++) {
for (int t2 = 0; t2 < 4; t2++) {
vii lower2 = lower;
sort(ALL(lower2));
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);
}
// the divider should intersect with exactly 4 vertical edges from both polygons
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();
}
