#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 100005;
const int oo = 1e9;
int n;
vector<pi> a;
lint ccw(pi a, pi b, pi c){
int dx1 = b.first - a.first;
int dy1 = b.second - a.second;
int dx2 = c.first - a.first;
int dy2 = c.second - a.second;
return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
void normalize(vector<pi> &v){
int minx = 1e9, miny = 1e9;
for(auto &i : v){
minx = min(minx, i.first);
miny = min(miny, i.second);
}
for(auto &i : v){
i.first -= minx;
i.second -= miny;
}
rotate(v.begin(), min_element(v.begin(), v.end()), v.end());
}
void reflect(vector<pi> &v){
for(auto &i : v){
i.first = -i.first;
}
normalize(v);
}
void turn(vector<pi> &v){
for(auto &i : v){
i = pi(-i.second, i.first);
}
normalize(v);
}
lint get_area(vector<pi> &v){
lint ret = 0;
for(int i=2; i<v.size(); i++){
ret += ccw(v[0], v[i-1], v[i]);
}
return ret;
}
bool hapdong(vector<pi> &v1, vector<pi> &v2){
normalize(v1);
normalize(v2);
for(int i=0; i<4; i++){
turn(v2);
if(v1 == v2) return 1;
}
reflect(v2);
for(int i=0; i<4; i++){
turn(v2);
if(v1 == v2) return 1;
}
reverse(v2.begin(), v2.end());
normalize(v2);
for(int i=0; i<4; i++){
turn(v2);
if(v1 == v2) return 1;
}
reflect(v2);
for(int i=0; i<4; i++){
turn(v2);
if(v1 == v2) return 1;
}
return 0;
}
bool mid(int s, int x, int e){
return 1ll * (e-x) * (x-s) >= 0;
}
bool smid(int s, int x, int e){
return 1ll * (e-x) * (x-s) > 0;
}
void cut_polygon(vector<pi> &in, vector<pi> &out1, vector<pi> &out2, int sx, int ex, int y){
if(get_area(in) < 0) reverse(in.begin(), in.end());
int p = min_element(in.begin(), in.end(), [&](const pi &a, const pi &b){
return a.second < b.second;
}) - in.begin();
if(in[p].second >= y){
out2 = in;
return;
}
int cpos = 0;
for(int i=0; i<in.size(); i++){
pi p1 = in[p%in.size()];
pi p2 = in[(p+1)%in.size()];
p++;
if(p1.second != p2.second && smid(p1.second, y, p2.second) && mid(sx, p1.first, ex)){
if(cpos == 0) out1.push_back(p1);
else out2.push_back(p1);
out1.push_back(pi(p1.first, y));
out2.push_back(pi(p1.first, y));
cpos ^= 1;
}
else if(p1.second == y && p2.second == y && (mid(sx, p1.first, ex) || mid(sx, p2.first, ex))){
if(sx != -1e9 && ex != 1e9 && smid(sx, p1.first, ex) && smid(sx, p2.first, ex)){
out1 = in;
out2.clear();
return;
}
if(cpos == 0) out1.push_back(p1);
else out2.push_back(p1);
cpos ^= 1;
}
else{
if(cpos == 0) out1.push_back(p1);
else out2.push_back(p1);
}
}
}
int rsx = -1, rsy = -1, rex = -1, rey = -1;
bool non_enclosing(int sx, int ex, int y){
for(int i=0; i<n; i++){
pi p1 = a[i];
pi p2 = a[(i+1)%n];
if(p1.second != y || p2.second != y) continue;
if(p1.first > p2.first) swap(p1, p2);
if(smid(sx, p1.first, ex) && smid(sx, p2.first, ex)) return 0;
}
return 1;
}
void save_results(int sx, int ex, int y){
for(int i=0; i<n; i++){
pi p1 = a[i];
pi p2 = a[(i+1)%n];
if(p1.second != y || p2.second != y) continue;
if(p1.first > p2.first) swap(p1, p2);
if(p1.first <= sx) sx = max(sx, p2.first);
if(p2.first >= ex) ex = min(ex, p1.first);
}
rsx = sx;
rex = ex;
rsy = y;
rey = y;
}
struct rect{
int sx, ex, sy, ey;
};
struct block{
int pos, s, e;
bool operator<(const block &b)const{
return pi(s, e) < pi(b.s, b.e);
}
};
struct swp{
int yc, xs, xe, act;
bool operator<(const swp &b)const{
return pi(yc, -act) < pi(b.yc, -b.act);
}
};
bool insec_by_edge(rect x, rect y){
x.sx = max(x.sx, y.sx);
x.ex = min(x.ex, y.ex);
x.sy = max(x.sy, y.sy);
x.ey = min(x.ey, y.ey);
if(x.sx > x.ex || x.sy > x.ey) return 0;
if(x.sx < x.ex && x.sy < x.ey) assert(0);
if(pi(x.sx, x.sy) == pi(x.ex, x.ey)) return 0;
return 1;
}
lint area[MAXN];
lint sum[MAXN], msz[MAXN];
vector<int> gph[MAXN];
void dfs(int x, int p){
sum[x] = area[x];
msz[x] = 0;
for(auto &i : gph[x]){
if(i != p){
dfs(i, x);
sum[x] += sum[i];
msz[x] = max(msz[x], sum[i]);
}
}
}
void solve(){
vector<swp> event;
set<block> s;
vector<rect> rect_list;
for(int i=0; i<n; i++){
pi p1 = a[i];
pi p2 = a[(i+1)%n];
if(p1.first == p2.first) continue;
if(p1.first < p2.first){
event.push_back({p1.second, p1.first, p2.first, +1});
}
else{
event.push_back({p1.second, p2.first, p1.first, -1});
}
}
sort(event.begin(), event.end());
auto rect_close = [&](block b, int pos){
if(b.pos < pos){
rect_list.push_back({b.s, b.e, b.pos, pos});
}
};
for(int i=0; i<event.size(); ){
int e = i;
while(e < event.size() && event[e].yc == event[i].yc){
if(event[e].act == 1){
auto lbnd = s.lower_bound({-1, event[e].xs, event[e].xe});
int curs = event[e].xs;
int cure = event[e].xe;
if(lbnd != s.begin() && prev(lbnd)->e == event[e].xs){
curs = prev(lbnd)->s;
rect_close(*prev(lbnd), event[e].yc);
s.erase(prev(lbnd));
}
if(lbnd != s.end() && lbnd->s == event[e].xe){
cure = lbnd->e;
rect_close(*lbnd, event[e].yc);
s.erase(lbnd);
}
s.insert({event[e].yc, curs, cure});
}
else{
auto lbnd = --s.lower_bound({-1, event[e].xe + 1, -1});
if(pi(lbnd->s, lbnd->e) == pi(event[e].xs, event[e].xe)){
rect_close(*lbnd, event[e].yc);
s.erase(lbnd);
}
else if(lbnd->s == event[e].xs){
rect_close(*lbnd, event[e].yc);
s.erase(lbnd);
s.insert({event[e].yc, event[e].xe, lbnd->e});
}
else if(lbnd->e == event[e].xe){
rect_close(*lbnd, event[e].yc);
s.erase(lbnd);
s.insert({event[e].yc, lbnd->s, event[e].xs});
}
else{
rect_close(*lbnd, event[e].yc);
block nxt1 = {event[e].yc, lbnd->s, event[e].xs};
block nxt2 = {event[e].yc, event[e].xe, lbnd->e};
s.erase(lbnd);
s.insert(nxt1);
s.insert(nxt2);
}
}
e++;
}
i = e;
}
for(int i=0; i<rect_list.size(); i++){
area[i] = 1ll * (rect_list[i].ex - rect_list[i].sx) * (rect_list[i].ey - rect_list[i].sy);
for(int j=0; j<i; j++){
if(insec_by_edge(rect_list[i], rect_list[j])){
gph[i].push_back(j);
gph[j].push_back(i);
}
}
}
dfs(0, -1);
if(sum[0] % 2) return;
for(int i=0; i<n; i++){
lint mxvi = max(msz[i], sum[0] - sum[i]);
if(mxvi <= sum[0] / 2){
lint lower_line = 0;
lint thres = sum[0] / 2;
for(auto &j : gph[i]){
if(rect_list[j].sy < rect_list[i].sy){
dfs(j, i);
lower_line += sum[j];
}
}
thres -= lower_line;
if(thres % (rect_list[i].ex - rect_list[i].sx) == 0){
lint mok = thres / (rect_list[i].ex - rect_list[i].sx);
mok += rect_list[i].sy;
vector<pi> v1, v2;
cut_polygon(a, v1, v2, rect_list[i].sx, rect_list[i].ex, mok);
if(hapdong(v1, v2)){
save_results(rect_list[i].sx, rect_list[i].ex, mok);
}
}
}
}
}
void point12(){
int s = 0, e = 1e9;
while(s != e){
int m = (s+e)/2;
vector<pi> v1, v2;
cut_polygon(a, v1, v2, -oo, oo, m);
if(abs(get_area(v1)) < abs(get_area(v2))){
s = m+1;
}
else e = m;
}
vector<pi> v1, v2;
cut_polygon(a, v1, v2, -oo, oo, s);
if(hapdong(v1, v2)){
vector<int> crd;
for(int i=0; i<n; i++){
pi p1 = a[i];
pi p2 = a[(i+1)%n];
if(p1.second == s && p2.second != s){
crd.push_back(p1.first);
}
if(p2.second == s && p1.second != s){
crd.push_back(p1.first);
}
if(smid(p1.second, s, p2.second)){
for(int i=0; i<2; i++) crd.push_back(p1.first);
}
}
sort(crd.begin(), crd.end());
save_results(crd[1], crd[2], s);
}
}
int main(){
scanf("%d",&n);
a.resize(n);
for(int i=0; i<n; i++){
scanf("%d %d",&a[i].first, &a[i].second);
}
for(int i=0; i<2; i++){
auto area = get_area(a);
if(area < 0) reverse(a.begin(), a.end());
solve();
if(i == 1) swap(rsx, rsy), swap(rex, rey);
if(rsx != -1){
printf("%d %d %d %d",rsx, rsy, rex, rey);
return 0;
}
for(int i=0; i<n; i++){
swap(a[i].first, a[i].second);
}
}
puts("NO");
}
Compilation message
demarcation.cpp: In function 'lint get_area(std::vector<std::pair<int, int> >&)':
demarcation.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=2; i<v.size(); i++){
~^~~~~~~~~
demarcation.cpp: In function 'void cut_polygon(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&, int, int, int)':
demarcation.cpp:98:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<in.size(); i++){
~^~~~~~~~~~
demarcation.cpp: In function 'void solve()':
demarcation.cpp:220:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<event.size(); ){
~^~~~~~~~~~~~~
demarcation.cpp:222:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(e < event.size() && event[e].yc == event[i].yc){
~~^~~~~~~~~~~~~~
demarcation.cpp:268:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<rect_list.size(); i++){
~^~~~~~~~~~~~~~~~~
demarcation.cpp: In function 'int main()':
demarcation.cpp:338:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
demarcation.cpp:341:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a[i].first, &a[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
3784 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
105 ms |
2736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1040 ms |
3772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
