#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()
int n, p, t, sgn, x[100005], y[100005], bit[100005];
vector<pair<int, pii> > v, w;
map<int, int> m, m2;
set<int> s;
ll c, ar, len;
void add(int P){
for (P=m[P]; P<=100000; P+=P&-P) bit[P]++;
}
int sum(int P, int V=0){
for (P=m[P]-1; P>0; P-=P&-P) V+=bit[P]; return V;
}
void flip(int X, int Y){
if (s.count(X)){
sgn=1; s.erase(X);
} else {
sgn=0; s.insert(X);
}
if (s.count(Y)) s.erase(Y);
else s.insert(Y);
if ((sum(X)+sgn)%2==0){
len+=Y-X;
} else {
len+=X-Y;
}
add(X); add(Y);
}
int main(){
scanf("%i", &n);
fox(l, n){
scanf("%i%i", &x[l], &y[l]);
m[y[l]]=0;
m2[x[l]]=0;
}
p=0; for (map<int, int>::iterator i=m.begin(); i!=m.end(); ++i) m[i->x]=++p;//, cout << i->x << ' ';
p=0; for (map<int, int>::iterator i=m2.begin(); i!=m2.end(); ++i) m2[i->x]=++p;
//cout << endl;
x[n]=x[0]; y[n]=y[0];
fox(l, n){
if (x[l]==x[l+1]){
v.pb(mp(x[l], mp(min(y[l], y[l+1]), max(y[l], y[l+1]))));
}
if (y[l]==y[l+1]){
w.pb(mp(y[l], mp(min(x[l], x[l+1]), max(x[l], x[l+1]))));
}
}
sort(v.begin(), v.end());
sort(w.begin(), w.end());
fox(l, v.size()-1){
flip(v[l].y.x, v[l].y.y);
c+=len*(v[l+1].x-v[l].x);
// cout << v[l].y.x << ' ' << v[l].y.y << ' ' << len << ' ' << c<< endl;
}
//return 0;
ar=c;
if (ar%2!=0){
cout << "NO";
return 0;
//impossible
}
c=0; len=0; drain(bit); s.clear();
fox(l, v.size()-1){
flip(v[l].y.x, v[l].y.y);
if (c*2<ar && 2*(c+len*(v[l+1].x-v[l].x))>=ar){
if (s.size()==2 && (c+len*(v[l+1].x-v[l].x)-ar/2)%len==0){
t=v[l+1].x-(c+len*(v[l+1].x-v[l].x)-ar/2)/len;
printf("%i %i %i %i", t, *s.begin(), t, *++s.begin());
return 0;
}
//break;
}
c+=len*(v[l+1].x-v[l].x);
//cout << len << ' ' << c << endl;
}
len=0; c=0; s.clear(); m=m2; drain(bit);
fox(l, w.size()-1){
flip(w[l].y.x, w[l].y.y);
if (c*2<ar && 2*(c+len*(w[l+1].x-w[l].x))>=ar){
if (s.size()==2 && (c+len*(w[l+1].x-w[l].x)-ar/2)%len==0){
t=w[l+1].x-(c+len*(w[l+1].x-w[l].x)-ar/2)/len;
printf("%i %i %i %i", *s.begin(), t, *++s.begin(), t);
return 0;
}
//break;
}
//cout << len << endl;
c+=len*(w[l+1].x-w[l].x);
}
//fail
cout << "NO";
return 0;
}
/*
10
0 0
1 0
1 1
3 1
3 7
2 7
2 4
1 4
1 3
0 3
*/
Compilation message
demarcation.cpp: In function 'int main()':
demarcation.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
demarcation.cpp:74:5: note: in expansion of macro 'fox'
fox(l, v.size()-1){
^
demarcation.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
demarcation.cpp:87:5: note: in expansion of macro 'fox'
fox(l, v.size()-1){
^
demarcation.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
demarcation.cpp:101:5: note: in expansion of macro 'fox'
fox(l, w.size()-1){
^
demarcation.cpp:54:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i", &n);
^
demarcation.cpp:56:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i", &x[l], &y[l]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
4012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
