#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
struct pt{
ll x,y;
pt(ll a=0,ll b=0):x(a),y(b){}
bool operator == (pt b)const{return mp(x,y)==mp(b.x,b.y);}
bool operator != (pt b)const{return mp(x,y)!=mp(b.x,b.y);}
bool operator < (pt b)const{return mp(x,y)<mp(b.x,b.y);}
};
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator -= (pt&a,pt b){return a=a-b;}
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator += (pt&a,pt b){return a=a+b;}
bool eq(vector<pt> a,vector<pt> b){
if(a.size()!=b.size())return 0;
for(int i=0;i<a.size();i++)if(a[i]!=b[i])return 0;
return 1;
}
void norm(vector<pt>&a){
int mn=0;
for(int i=0;i<a.size();i++)if(a[i]<a[mn])mn=i;
vector<pt> tmp;
for(int i=0;i<a.size();i++)tmp.pb(a[(mn+i)%a.size()]);
a=tmp;
if(a[1].x==a[0].x)reverse(a.begin()+1,a.end());
for(int i=1;i<a.size();i++)a[i]-=a[0];
a[0]=pt(0,0);
}
void rotate(vector<pt>&a){
for(pt&p:a)p=pt(-p.y,p.x);
}
void mirror(vector<pt>&a){
for(pt&p:a)p=pt(-p.x,p.y);
}
bool on_line(pt a,pt b,pt c){
return (a.x==b.x&&a.x==c.x)||(a.y==b.y&&a.y==c.y);
}
void pop(vector<pt>&a){
while(a.size()>3&&on_line(a.back(),a[0],a[1]))a.erase(a.begin());
while(a.size()>3&&on_line(a[0],a.back(),a[(int)a.size()-2]))a.pop_back();
}
pt min_pt(vector<pt> a){
pt ans=a[0];
for(pt p:a)ans=min(ans,p);
return ans;
}
bool Check(vector<pt> a,vector<pt> b){
if(a.size()!=b.size())return 0;
norm(a);
for(int i=0;i<2;i++){
for(int j=0;j<4;j++){
norm(b);
if(eq(a,b))return 1;
rotate(b);
}
mirror(b);
}
return 0;
}
struct seg{
pt a,b;
seg(){}
seg(pt x,pt y):a(x),b(y){}
int type(){
if(a.y==b.y)return a.x<b.x?-1:1;
if(a.x==b.x)return a.y<b.y?2:3;
}
ll get(){
return a.y*(a.x-b.x);
}
};
const int N=200050;
seg s[N];
ll sum[N];
bool Solve(vector<pt> a,seg&ans){
for(int i=0;i<a.size();i++){
int j=(i+1)%a.size();
s[i+1]=seg(a[i],a[j]);
}
for(int i=1;i<=a.size();i++)sum[i]=sum[i-1]+s[i].get();
int hal=a.size()/2;
ll area=sum[a.size()];
//printf("%lld\n",area);
if(area&1)return 0;
assert(area>0);
for(int i=1;i<=a.size();i++)if(s[i].type()==2){
for(int z=-3;z<=3;z++){
int j=(i-1+hal+z+a.size())%a.size()+1;
if(s[j].type()==3&&s[j].a.x<s[i].a.x){
//printf("%i - %i\n",i,j);
ll A=sum[j]+(j<i?sum[a.size()]-sum[i-1]:-sum[i-1]);
//printf("A: %lld\n",A);
if(A<area/2)continue;
ll dif=A-area/2;
ll rng=s[i].a.x-s[j].a.x;
//printf("dif:%lld rng:%lld\n",dif,rng);
if(dif%rng!=0)continue;
ll H=dif/rng;
if(s[i].a.y<=H&&s[i].b.y>=H&&s[j].b.y<=H&&s[j].a.y>=H){
//printf(":D H:%lld\n",H);
pt o1(s[i].a.x,H),o2(s[j].a.x,H);
vector<pt> p1,p2;
for(int i1=i;i1!=j;i1=i1==a.size()?1:i1+1){
p1.pb(s[i1].b);
}
if(p1.back()!=o2)p1.pb(o2);
if(p1.front()!=o1)p1.pb(o1);
for(int i2=j;i2!=i;i2=i2==a.size()?1:i2+1){
p2.pb(s[i2].b);
}
if(p2.back()!=o1)p2.pb(o1);
if(p2.front()!=o2)p2.pb(o2);
pop(p1);pop(p2);
//for(pt p:p1)printf("(%lld %lld) ",p.x,p.y);printf("\n");
//for(pt p:p2)printf("(%lld %lld) ",p.x,p.y);printf("\n");
if(Check(p1,p2)){
ans=seg(o1,o2);
return 1;
}
}
}
}
}
return 0;
}
int main(){
int n;
scanf("%i",&n);
vector<pt> a(n);
for(pt&p:a)scanf("%lld %lld",&p.x,&p.y);
pt add=min_pt(a);
seg ans;
norm(a);
//for(pt p:a)printf("(%lld %lld) ",p.x,p.y);printf("\n");
if(Solve(a,ans)){
ans.a+=add;
ans.b+=add;
printf("%lld %lld %lld %lld\n",ans.a.x,ans.a.y,ans.b.x,ans.b.y);
return 0;
}
rotate(a);
pt add2=min_pt(a);
norm(a);
if(Solve(a,ans)){
ans.a+=add2;
ans.b+=add2;
vector<pt> sol={ans.a,ans.b};
for(int i=0;i<3;i++)rotate(sol);
sol[0]+=add;
sol[1]+=add;
printf("%lld %lld %lld %lld\n",sol[0].x,sol[0].y,sol[1].x,sol[1].y);
return 0;
}
printf("NO\n");
return 0;
}
Compilation message
demarcation.cpp: In function 'bool eq(std::vector<pt>, std::vector<pt>)':
demarcation.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i=0;i<a.size();i++)if(a[i]!=b[i])return 0;
| ~^~~~~~~~~
demarcation.cpp: In function 'void norm(std::vector<pt>&)':
demarcation.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i=0;i<a.size();i++)if(a[i]<a[mn])mn=i;
| ~^~~~~~~~~
demarcation.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i=0;i<a.size();i++)tmp.pb(a[(mn+i)%a.size()]);
| ~^~~~~~~~~
demarcation.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=1;i<a.size();i++)a[i]-=a[0];
| ~^~~~~~~~~
demarcation.cpp: In function 'bool Solve(std::vector<pt>, seg&)':
demarcation.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
demarcation.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i=1;i<=a.size();i++)sum[i]=sum[i-1]+s[i].get();
| ~^~~~~~~~~~
demarcation.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i=1;i<=a.size();i++)if(s[i].type()==2){
| ~^~~~~~~~~~
demarcation.cpp:106:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i1=i;i1!=j;i1=i1==a.size()?1:i1+1){
| ~~^~~~~~~~~~
demarcation.cpp:111:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i2=j;i2!=i;i2=i2==a.size()?1:i2+1){
| ~~^~~~~~~~~~
demarcation.cpp: In member function 'int seg::type()':
demarcation.cpp:70:2: warning: control reaches end of non-void function [-Wreturn-type]
70 | }
| ^
demarcation.cpp: In function 'int main()':
demarcation.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
131 | scanf("%i",&n);
| ~~~~~^~~~~~~~~
demarcation.cpp:133:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
133 | for(pt&p:a)scanf("%lld %lld",&p.x,&p.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7640 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
7504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6528 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 5 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 6 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 8 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 9 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 10 |
Incorrect |
4 ms |
6528 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 5 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 6 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 8 |
Correct |
4 ms |
6656 KB |
Output is correct |
| 9 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 10 |
Correct |
5 ms |
6528 KB |
Output is correct |
| 11 |
Incorrect |
4 ms |
6656 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7640 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6596 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6528 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
7504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
