#include "bits/stdc++.h"
// #include "geodeb.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e18;
typedef complex<ll> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
auto norm(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
void read(pt& p) {
int a,b; cin >> a >> b;
p = {a,b};
}
bool comp(const pt& a, const pt& b) {
return a.X < b.X or (a.X==b.X and a.Y < b.Y);
}
typedef vector<pt> polygon;
void normalize(polygon& a) {
int ans = 0;
for(int i=1;i<(int)a.size();++i) {
if(comp(a[i],a[ans])) {
ans= i;
}
}
if(ans!=0)
rotate(a.begin(), a.begin()+ans, a.end());
pt delta = a[0];
for(auto& p : a) p-=delta;
}
bool equal(polygon& a, polygon& b) {
normalize(a);
normalize(b);
// GD_LAYER();
// GD_POLYGON("black:purple",
// for(auto& p: a) {
// // GD_POLYPOINT(p.X,p.Y);
// }
// );
// // GD_PAUSE();
// // GD_POLYGON("black:orange",
// for(auto& p: b) {
// // GD_POLYPOINT(p.X,p.Y);
// }
// );
return a==b;
}
bool congruent(polygon a, polygon b) {
if(a.size()!=b.size()) return false;
for(int j=0;j<2;++j) {
for(int i=0;i<4;++i) {
if(equal(a,b)) return true;
if(i<3) for(auto& p : a) p *= pt{0,1};
}
if(!j) {for(auto& p : a) p = conj(p);
reverse(all(a));
}
}
return false;
}
pt aa=0, bb=0;
bool good = false;
polygon poly;
bool check(int x, int i, int j) {
polygon a, b;
assert(poly[i].Y<poly[j].Y);
int n = poly.size();
if(j<i) {
for(int k=j;k<=i;++k) {
a.push_back(poly[k]);
}
for(int k=i+1;k<n;++k) b.push_back(poly[k]);
for(int k=0;k<j;++k) {
b.push_back(poly[k]);
}
} else {
for(int k=i+1;k<j;++k) {
b.push_back(poly[k]);
}
for(int k=j;k<n;++k) a.push_back(poly[k]);
for(int k=0;k<=i;++k) {
a.push_back(poly[k]);
}
}
if(a.empty() or b.empty()) return false;
auto add = [](polygon& a, pt cc) {
a.push_back(cc);
};
pt c = {x,poly[i].Y}, d = {x,poly[j].Y} ;
add(a,c);
add(a,d);
add(b,d);
add(b,c);
auto repair = [](polygon& a) {
while(a.size()> 3 and ccw(a[a.size()-2], a.back(), a[0])==0) {
a.pop_back();
}
int i=0;
while(a.size()-i>3 and ccw(a.back(),a[i],a[i+1])==0) {
++i;
}
a.erase(a.begin(),a.begin()+i);
};
repair(a); repair(b);
// // GD_LAYER();
// // GD_POLYGON("black:purple",
// for(auto& p: a) {
// // GD_POLYPOINT(p.X,p.Y);
// }
// );
// // GD_PAUSE();
// // GD_POLYGON("black:orange",
// for(auto& p: b) {
// // GD_POLYPOINT(p.X,p.Y);
// }
// );
bool yes = congruent(a,b);
if(yes) {
aa = c; bb = d;
}
return yes;
}
ll getarea() {
int n = poly.size();
int j = n-1;
ll ans = 0;
for(int i=1;i<n;++i) {
ans+=(ll)(poly[i].Y+poly[j].Y)*(poly[i].X-poly[j].Y);
j=i;
}
return ans/2;
}
struct event {
ll x;
int id1, id2;
bool end, top, in = false,split=false;
bool operator<(const event& o) const {
// All directions reversed;
if(x!=o.x)
return x > o.x;
if(in!=o.in) return in<o.in;
return (split<o.split);
}
};
ll pref[mxN], total=0;
ll findx(int i, int j, ll x) {
ll got=0;
if(i>j) {
got = pref[i]-pref[j];
} else {
got = pref[i]+(total-pref[j]);
}
got+=2*x - poly[i].X - poly[j].X;
if(total%2==1) return oo;
ll need = total/2-got;
if(need%2==1 or need<0) return oo;
return x+need/2;
}
int main() {
// GD_INIT("demarc.html");
int n; cin >> n;
poly.resize(n);
for(auto& p: poly) read(p);
ll area = getarea();
if(area>0) {
reverse(all(poly));
}
for(int i=1;i<n;++i) {
int len = abs(poly[i]-poly[i-1]);
pref[i]=pref[i-1]+len;
total+=len;
}
total+=abs(poly[0]-poly[n-1]);
for(int rep=0;rep<2;++rep) {
priority_queue<event> events;
// GD_LAYER();
auto& mypoly = poly;
// GD_POLYGON("black:salmon",
// for(int i=0;i<n;++i) {
// // GD_POLYPOINT(mypoly[i].X,mypoly[i].Y);
// }
// );
int j = n-1;
for(int i=0;i<n;++i) {
if(poly[i].Y==poly[j].Y) {
int c = poly[i].X, d = poly[j].X;
bool swapped=false;
int f = i;
int nxt = (i+1)%n;
if(c>d) {
f = j;
nxt = (j-1+n)%n;
swap(c,d);
swapped = true;
}
bool bin = poly[f].Y<poly[nxt].Y;
events.push({c, f,0,false,!swapped, bin!=swapped});
events.push({d, f,0,true, !swapped, bin==swapped});
}
j=i;
}
struct el {
int i;
bool top;
bool operator<(const el& o) const {
return poly[i].Y < poly[o.i].Y or (poly[i].Y == poly[o.i].Y and i<o.i);
}
bool operator<(int o) const {
return poly[i].Y < poly[o].Y or (poly[i].Y == poly[o].Y and i<o);
}
};
set<el> s;
while(!events.empty()) {
auto e = events.top(); events.pop();
if(e.split) {
// GD_SEGMENT(e.x,poly[e.id1].Y, e.x, poly[e.id2].Y, "green");
// GD_PAUSE();
auto iter = s.find({e.id1,false});
auto iter2 = s.find({e.id2,false});
if(iter==s.end() or iter2==s.end()) {
continue;
}
auto iter3 = iter; iter3++;
if(iter3!=iter2) {
continue;
}
if(check(e.x, iter->i, iter2->i)) {
good = true;
}
break;
} else {
// GD_POINT(e.x, poly[e.id1].Y, e.top?"blue":"red");
if(e.end) {
s.erase({e.id1,false});
} else {
auto [iter,haha] = s.insert({e.id1,e.top});
if(e.top) {
iter--;
if(iter!=s.end() and iter->top!=e.top) {
auto x = findx(iter->i,e.id1,e.x);
if(x<oo)
events.push(event{x,iter->i, e.id1,false,false,false,true });
}
} else {
iter++;
if(iter!=s.end() and iter->top!=e.top) {
auto x = findx(e.id1,iter->i,e.x);
if(x<oo)
events.push(event{x,e.id1,iter->i,false,false,false,true });
}
}
}
}
}
if(rep==1) {
aa/=pt{0,1};
bb/=pt{0,1};
}
if(good) break;
if(!rep) for(auto& p : poly) p*=pt{0,1};
}
if(good) {
cout << aa.X << ' ' << aa.Y << ' ' << bb.X << ' ' << bb.Y;
} else {
cout << "NO\n";
}
}
Compilation message
demarcation.cpp: In function 'int main()':
demarcation.cpp:196:15: warning: unused variable 'mypoly' [-Wunused-variable]
196 | auto& mypoly = poly;
| ^~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
1368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
1368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
