#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point {
ll x, y;
point operator-(point outro) {
point novo;
novo.x=x-outro.x;
novo.y=y-outro.y;
return novo;
}
};
const int MAXN=1e5+5;
point p[MAXN];
int n;
ll tudo;
ll mnx, mny, mxx, mxy;
ll area(ll val, int k) {
ll resp=0;
for(int i=3; i<=n; i++) {
point a=p[i]; point b=p[i-1];
if(k==1) a.x=min(a.x, val), b.x=min(b.x, val);
if(k==2) a.y=min(a.y, val), b.y=min(b.y, val);
a=a-p[1]; b=b-p[1];
resp+=(a.x*b.y)-(a.y*b.x);
}
// printf("area %lld %d > %lld\n", val, k, abs(resp)/2);
return abs(resp)/2;
}
bool testa(ll corte, int k) {
if(area(corte, k)!=tudo/2) return 0;
multiset<ll> s, s2;
// printf("testa corte=%lld k=%d\n", corte, k);
ll ini=-1; ll fim=-1;
ll ini2=-1; ll fim2=-1;
//parte esquerda e direita
if(k==1) {
for(int i=1; i<=n; i++) {
point cur=p[i]; point anter= i==1 ? p[n] : p[i-1];
ll val=abs(cur.x-anter.x)+abs(cur.y-anter.y);
// printf("%d: %lld // cmp (%lld %lld) <-> (%lld %lld)\n", i, val, cur.x, cur.y, anter.x, anter.y);
if(anter.x==cur.x) {
if(anter.x<corte) s.insert(val);
if(anter.x>corte) s2.insert(val);
continue;
}
if(corte<anter.x&&corte<cur.x) s2.insert(val);
else if(corte>anter.x&&corte>cur.x) s.insert(val);
else if(anter.x<=cur.x&&corte<=cur.x) s.insert(val-abs(cur.x-corte)), s2.insert(abs(cur.x-corte));
else s.insert(abs(cur.x-corte)), s2.insert(val-abs(cur.x-corte));
if((cur.x<=corte&&anter.x<=corte&&(cur.x==corte||anter.x==corte))||min(cur.x, anter.x)<corte&&max(cur.x, anter.x)>corte) {
if(ini>=0&&fim==-1) s.insert(abs(cur.y-ini)), fim=cur.y;
else if(ini==-1) ini=cur.y;
}
if((cur.x>=corte&&anter.x>=corte&&(cur.x==corte||anter.x==corte))||min(cur.x, anter.x)<corte&&max(cur.x, anter.x)>corte) {
if(ini2>=0&&fim2==-1) s2.insert(abs(cur.y-ini2)), fim2=cur.y;
else if(ini2==-1) ini2=cur.y;
}
}
}
//parte direita/superior
if(k==2) {
for(int i=1; i<=n; i++) {
point cur=p[i]; point anter= i==1 ? p[n] : p[i-1];
ll val=abs(cur.x-anter.x)+abs(cur.y-anter.y);
// printf("%d: %lld // cmp (%lld %lld) <-> (%lld %lld)\n", i, val, cur.x, cur.y, anter.x, anter.y);
if(anter.y==cur.y) {
if(anter.y<corte) s.insert(val);
if(anter.y>corte) s2.insert(val);
continue;
}
if(corte<anter.y&&corte<cur.y) s2.insert(val);
else if(corte>anter.y&&corte>cur.y) s.insert(val);
else if(anter.y<=cur.y&&corte<=cur.y) s.insert(val-abs(cur.y-corte)), s2.insert(abs(cur.y-corte));
else s.insert(abs(cur.y-corte)), s2.insert(val-abs(cur.y-corte));
if((cur.y<=corte&&anter.y<=corte&&(cur.y==corte||anter.y==corte))||min(cur.y, anter.y)<corte&&max(cur.y, anter.y)>corte) {
if(ini>=0&&fim==-1) s.insert(abs(cur.x-ini)), fim=cur.x;
else if(fim==-1) ini=cur.x;
}
if((cur.y>=corte&&anter.y>=corte&&(cur.y==corte||anter.y==corte))||min(cur.y, anter.y)<corte&&max(cur.y, anter.y)>corte) {
if(ini2>=0&&fim2==-1) s2.insert(abs(cur.x-ini2)), fim2=cur.x;
else if(fim2==-1) ini2=cur.x;
}
// printf(" marcs %lld %lld\n", marc, marc2);
}
}
// printf("///s: "); for(auto cur : s) printf("%lld ", cur); printf("\n");
// printf("///s2: "); for(auto cur : s2) printf("%lld ", cur); printf("\n");
s.erase(0); s2.erase(0);
if(s==s2) {
if(abs(fim-ini)>abs(ini2-fim2)) ini2=ini, fim2=fim;
if(k==1) printf("%lld %lld %lld %lld\n", corte, ini2, corte, fim2);
if(k==2) printf("%lld %lld %lld %lld\n", ini2, corte, fim2, corte);
return 1;
}
return 0;
}
int main() {
scanf("%d", &n);
for(int i=1; i<=n; i++) {
scanf("%lld %lld", &p[i].x, &p[i].y);
mnx=min(mnx, p[i].x); mxx=max(mxx, p[i].x);
mny=min(mny, p[i].y); mxy=max(mxy, p[i].y);
}
tudo=area(mxx, -1);
// printf("area= %lld\n", tudo);
// testa vertical
int ind=mnx; for(int i=mxx; i>0; i/=2) while(ind+i<=mxx&&area(ind+i, 1)<=tudo/2) ind+=i; //printf("vert ind= %d > %lld\n", ind, area(ind, 1));
if(testa(ind, 1)) return 0;
// testa horizontal
ind=mny; for(int i=mxy; i>0; i/=2) while(ind+i<=mxy&&area(ind+i, 2)<=tudo/2) ind+=i; //printf("horiz ind= %d > %lld\n", ind, area(ind, 2));
if(testa(ind, 2)) return 0;
printf("NO\n");
}
Compilation message
demarcation.cpp: In function 'bool testa(ll, int)':
demarcation.cpp:59:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if((cur.x<=corte&&anter.x<=corte&&(cur.x==corte||anter.x==corte))||min(cur.x, anter.x)<corte&&max(cur.x, anter.x)>corte) {
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp:63:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if((cur.x>=corte&&anter.x>=corte&&(cur.x==corte||anter.x==corte))||min(cur.x, anter.x)<corte&&max(cur.x, anter.x)>corte) {
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp:89:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if((cur.y<=corte&&anter.y<=corte&&(cur.y==corte||anter.y==corte))||min(cur.y, anter.y)<corte&&max(cur.y, anter.y)>corte) {
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp:93:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if((cur.y>=corte&&anter.y>=corte&&(cur.y==corte||anter.y==corte))||min(cur.y, anter.y)<corte&&max(cur.y, anter.y)>corte) {
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp: In function 'int main()':
demarcation.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
demarcation.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &p[i].x, &p[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
