#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
using namespace std;
///~~~~~~~~~~~~~~~~~~~~~~~~~~
template <typename H, typename T>
ostream& operator<<(ostream& os, pair<H, T> m){
return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H>
ostream& operator<<(ostream& os, vector<H> V){
os<<"{";
for(int i=0; i<V.size(); i++){
if(i)os<<" ";
os<<V[i];
}
os<<"}";
return os;
}
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
///~~~~~~~~~~~~~~~~~~~~~~~~~
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int K=18, N=(1<<K), INF=1e9+5, mod=1e9+7, mod2=998244353;
struct modint{
int n=0;
modint(){}
modint(ll x){
n=x%mod;
if(n<0)n+=mod;
}
operator int(){
return n;
}
modint operator+(modint a){a.n = n+a.n; if(a.n>=mod)a.n-=mod;return a;}
modint operator+=(modint a){return (*this)=(*this)+a;}
modint operator-(modint a){a.n = n-a.n; if(a.n<0)a.n+=mod;return a;}
modint operator-=(modint a){return (*this)=(*this)-a;}
modint operator*(modint a){a.n = (n*1ll*a.n)%mod; return a;}
modint operator*=(modint a){return (*this)=(*this)*a;}
modint operator^(const ll &m)const{
modint a(1);
if(m==0)return a;
if(m==1)return (*this);
a=(*this)^(m/2);
a*=a;
return a*((*this)^(m&1));
}
modint odw(){
return (*this)^((ll)mod-2);
}
modint operator/(modint a){return (*this)*a.odw();}
modint operator/=(modint a){return (*this)=(*this)/a;}
bool operator==(modint a){return a.n==n;}
friend ostream& operator<<(ostream& os, modint m) {
return os << m.n;
}
};
modint fact[N], fact2[N];
typedef vector<modint> vm;
void factinit(){
fact[0]=1;
for(int i=1; i<N; i++){
fact[i]=(fact[i-1]*modint(i))%mod;
}
fact2[N-1]=fact[N-1].odw();
for(int i=N-2; i>=0; i--){
fact2[i]=(fact2[i+1]*modint(i+1))%mod;
}
}
modint npok(int _n, int _k){
return fact[_n]*fact2[_k]*fact2[_n-_k];
}
void refx(vii &V){for(pii &i:V)i.nd=-i.nd;}
void refy(vii &V){for(pii &i:V)i.st=-i.st;}
void refxy(vii &V){for(pii &i:V)swap(i.st, i.nd);}
bool cmp(vii &V, vii &V2){
int m1=0, m2=0;
for(int i=0; i<V.size(); i++)if(V[i]<V[m1])m1=i;
for(int i=0; i<V.size(); i++)if(V2[i]<V2[m2])m2=i;
int x=V[m1].st-V2[m2].st, y=V[m1].nd-V2[m2].nd;
for(int i=0;i<V.size(); i++){
if(V[m1].st-x!=V2[m2].st || V[m1].nd-y!=V2[m2].nd){
return 0;
}
if(++m1>=V.size())m1=0;
if(++m2>=V.size())m2=0;
}
return 1;
}
bool row(vii &V, vii &V2){
//deb(V, V2);
if(cmp(V, V2))return 1;refx(V);
if(cmp(V, V2))return 1;refy(V);
if(cmp(V, V2))return 1;refx(V);
if(cmp(V, V2))return 1;refxy(V);
//deb(V, V2);
if(cmp(V, V2))return 1;refy(V);
if(cmp(V, V2))return 1;refx(V);
if(cmp(V, V2))return 1;refy(V);
if(cmp(V, V2))return 1;refxy(V);
rev(V);
if(cmp(V, V2))return 1;refx(V);
if(cmp(V, V2))return 1;refy(V);
if(cmp(V, V2))return 1;refx(V);
if(cmp(V, V2))return 1;refxy(V);
//deb(V, V2);
if(cmp(V, V2))return 1;refy(V);
if(cmp(V, V2))return 1;refx(V);
if(cmp(V, V2))return 1;refy(V);
if(cmp(V, V2))return 1;refxy(V);
//deb(V, V2);
return 0;
}
pair<bool, pair<pii, pii>> solve(vii &V){
pair<bool, pair<pii, pii>> nie={0, {{0, 0}, {0, 0}}};
int n=V.size();
if(V[0].nd!=V[1].nd){
for(int i=0; i<n-1; i++)swap(V[i], V[i+1]);
}
ll A=0, A2=0;
for(int i=0; i<n; i+=2){
A+=(V[i+1].st-V[i].st)*1ll*V[i].nd;
deb((V[i+1].st-V[i].st)*1ll*V[i].nd);
if(i<=n/2)A2+=(V[i+1].st-V[i].st)*1ll*V[i].nd;
}
if(A&1)return nie;
A/=2;
if(n&2){
for(int i=1; i<n; i+=2){
A2-=(V[i].st-V[i-1].st)*1ll*V[i].nd;
int j=(i+n/2)%n;
if((V[j].st-V[i].st)*1ll*(V[i].st-V[i-1].st)>0 && (A-A2)%(V[i].st-V[j].st)==0){
int h=(A-A2)/(V[i].st-V[j].st);
if(h==V[i].nd){
deb(i);
vector<pii> V2, V3;
for(int k=i; k!=j; k=(k+1)%n){
V2.pb(V[k]);
}
V2.eb(V[j].st, h);
V3.eb(V[j].st, h);
for(int k=j; k!=i; k=(k+1)%n){
V3.pb(V[k]);
}
deb(V2, V3);
if(row(V2, V3)){
bool b=1;
for(int k=0; k<n; k+=2){
if(V[k].nd==h && min(max(V[k].st, V[k+1].st), max(V[i].st, V[j].st))>
max(min(V[k].st, V[k+1].st), min(V[i].st, V[j].st)))b=0;
if(min(V[i].st, V[j].st)<V[k+1].st && min(V[i].st, V[j].st) >V[k+1].st &&
min(V[k+1].nd, V[(k+2)%n].nd)<h && max(V[k+1].nd, V[(k+2)%n].nd)>h)b=0;
}
if(b)return {1, {V[i], {V[j].st, h}}};
}
}
}
A2+=(V[j+1].st-V[j].st)*1ll*V[j].nd;
}
}
else{
deb(A, A2);
for(int i=1; i<n; i+=2){
A2-=(V[i].st-V[i-1].st)*1ll*V[i].nd;
int j=(i+n/2)%n;
deb(i, j, A2);
if(V[i].st!=V[j].st && (A-A2)%(V[i].st-V[j].st)==0){
deb(i, j);
int h=(A-A2)/(V[i].st-V[j].st);
deb(h);
if(h>=min(V[i].nd, V[(i+1)%n].nd) && h<=max(V[i].nd, V[(i+1)%n].nd)
&& h>=min(V[j].nd, V[(j+1)%n].nd) && h<=max(V[j].nd, V[(j+1)%n].nd)){
//deb(i);
vector<pii> V2, V3;
V2.pb({V[i].st, h});
if(V[(i+1)%n].nd!=h)V2.pb(V[(i+1)%n]);
for(int k=(i+1)%n; k!=j%n; k=(k+1)%n){
if(k!=(i+1)%n)V2.pb(V[k]);
}
if(V[j].nd!=h)V2.pb(V[j]);
V2.eb(V[j].st, h);
V3.pb({V[j].st, h});
if(V[(j+1)%n].nd!=h)V3.pb(V[(j+1)%n]);
for(int k=(j+1)%n; k!=i%n; k=(k+1)%n){
if(k!=(j+1)%n)V3.pb(V[k]);
}
if(V[i].nd!=h)V3.pb(V[i]);
V3.eb(V[i].st, h);
//deb(V2, V3);
if(row(V2, V3)){
bool b=1;
for(int k=0; k<n; k+=2){
if(V[k].nd==h && min(max(V[k].st, V[k+1].st), max(V[i].st, V[j].st))>
max(min(V[k].st, V[k+1].st), min(V[i].st, V[j].st)))b=0;
if(min(V[i].st, V[j].st)<V[k+1].st && min(V[i].st, V[j].st) >V[k+1].st &&
min(V[k+1].nd, V[(k+2)%n].nd)<h && max(V[k+1].nd, V[(k+2)%n].nd)>h)b=0;
}
if(b)return {1, {{V[i].st, h}, {V[j].st, h}}};
}
}
}
A2+=(V[(j+2)%n].st-V[(j+1)%n].st)*1ll*V[(j+1)%n].nd;
}
}
return nie;
}
int main(){
//factinit();
//BOOST;
int n;
cin>>n;
vii V(n);
for(auto &i:V)cin>>i.st>>i.nd;//, i.st*=2, i.nd*=2;
auto t=solve(V);
//return 0;
deb("a", t.st);
if(t.st==0){
refxy(V);
t=solve(V);
swap(t.nd.st.st, t.nd.st.nd);
swap(t.nd.nd.st, t.nd.nd.nd);
}
deb("a", t.st);
if(t.st==0){
refxy(V);
rev(V);
t=solve(V);
}
deb("a", t.st);
if(t.st==0){
refxy(V);
t=solve(V);
swap(t.nd.st.st, t.nd.st.nd);
swap(t.nd.nd.st, t.nd.nd.nd);
}
if(t.st==0)cout<<"NO\n";
else{
//cout<<ld(t.nd.st.st)/2<<" "<<ld(t.nd.st.nd)/2<<" "<<ld(t.nd.nd.st)/2<<" "<<ld(t.nd.nd.nd)/2;
cout<<t.nd.st.st<<" "<<t.nd.st.nd<<" "<<t.nd.nd.st<<" "<<t.nd.nd.nd;
}
}
Compilation message
demarcation.cpp: In function 'bool cmp(vii&, vii&)':
demarcation.cpp:114:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i=0; i<V.size(); i++)if(V[i]<V[m1])m1=i;
| ~^~~~~~~~~
demarcation.cpp:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i=0; i<V.size(); i++)if(V2[i]<V2[m2])m2=i;
| ~^~~~~~~~~
demarcation.cpp:117:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i=0;i<V.size(); i++){
| ~^~~~~~~~~
demarcation.cpp:121:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | if(++m1>=V.size())m1=0;
| ~~~~^~~~~~~~~~
demarcation.cpp:122:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | if(++m2>=V.size())m2=0;
| ~~~~^~~~~~~~~~
demarcation.cpp: In function 'bool row(vii&, vii&)':
demarcation.cpp:128:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
128 | if(cmp(V, V2))return 1;refx(V);
| ^~
demarcation.cpp:128:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
128 | if(cmp(V, V2))return 1;refx(V);
| ^~~~
demarcation.cpp:129:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
129 | if(cmp(V, V2))return 1;refy(V);
| ^~
demarcation.cpp:129:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
129 | if(cmp(V, V2))return 1;refy(V);
| ^~~~
demarcation.cpp:130:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
130 | if(cmp(V, V2))return 1;refx(V);
| ^~
demarcation.cpp:130:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
130 | if(cmp(V, V2))return 1;refx(V);
| ^~~~
demarcation.cpp:131:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
131 | if(cmp(V, V2))return 1;refxy(V);
| ^~
demarcation.cpp:131:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
131 | if(cmp(V, V2))return 1;refxy(V);
| ^~~~~
demarcation.cpp:133:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
133 | if(cmp(V, V2))return 1;refy(V);
| ^~
demarcation.cpp:133:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
133 | if(cmp(V, V2))return 1;refy(V);
| ^~~~
demarcation.cpp:134:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
134 | if(cmp(V, V2))return 1;refx(V);
| ^~
demarcation.cpp:134:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
134 | if(cmp(V, V2))return 1;refx(V);
| ^~~~
demarcation.cpp:135:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
135 | if(cmp(V, V2))return 1;refy(V);
| ^~
demarcation.cpp:135:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
135 | if(cmp(V, V2))return 1;refy(V);
| ^~~~
demarcation.cpp:136:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
136 | if(cmp(V, V2))return 1;refxy(V);
| ^~
demarcation.cpp:136:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
136 | if(cmp(V, V2))return 1;refxy(V);
| ^~~~~
demarcation.cpp:138:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
138 | if(cmp(V, V2))return 1;refx(V);
| ^~
demarcation.cpp:138:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
138 | if(cmp(V, V2))return 1;refx(V);
| ^~~~
demarcation.cpp:139:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
139 | if(cmp(V, V2))return 1;refy(V);
| ^~
demarcation.cpp:139:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
139 | if(cmp(V, V2))return 1;refy(V);
| ^~~~
demarcation.cpp:140:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
140 | if(cmp(V, V2))return 1;refx(V);
| ^~
demarcation.cpp:140:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
140 | if(cmp(V, V2))return 1;refx(V);
| ^~~~
demarcation.cpp:141:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
141 | if(cmp(V, V2))return 1;refxy(V);
| ^~
demarcation.cpp:141:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
141 | if(cmp(V, V2))return 1;refxy(V);
| ^~~~~
demarcation.cpp:143:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
143 | if(cmp(V, V2))return 1;refy(V);
| ^~
demarcation.cpp:143:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
143 | if(cmp(V, V2))return 1;refy(V);
| ^~~~
demarcation.cpp:144:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
144 | if(cmp(V, V2))return 1;refx(V);
| ^~
demarcation.cpp:144:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
144 | if(cmp(V, V2))return 1;refx(V);
| ^~~~
demarcation.cpp:145:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
145 | if(cmp(V, V2))return 1;refy(V);
| ^~
demarcation.cpp:145:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
145 | if(cmp(V, V2))return 1;refy(V);
| ^~~~
demarcation.cpp:146:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
146 | if(cmp(V, V2))return 1;refxy(V);
| ^~
demarcation.cpp:146:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
146 | if(cmp(V, V2))return 1;refxy(V);
| ^~~~~
demarcation.cpp: In instantiation of 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>) [with H = std::pair<int, int>; std::ostream = std::basic_ostream<char>]':
demarcation.cpp:39:30: required from 'void debug(H, T ...) [with H = std::vector<std::pair<int, int> >; T = {std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >}]'
demarcation.cpp:182:6: required from here
demarcation.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
3552 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2356 KB |
Output is correct |
| 4 |
Incorrect |
266 ms |
4004 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2356 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2360 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
2260 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
2260 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
186 ms |
3540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2260 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2312 KB |
Output is correct |
| 4 |
Incorrect |
267 ms |
4084 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
