#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
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;
}
void debug(vector<pi> &v){
printf("%d ", v.size());
for(auto &i : v) printf("(%d, %d) ", i.first, i.second);
puts("");
}
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(p2);
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);
}
}
// printf("%d %d %d %d\n",sx,ex,sy,ey);
// debug(out1), debug(out2);
}
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 swp{
int yc, xc, act;
bool operator<(const swp &b)const{
return yc < b.yc;
}
};
void solve(){
vector<swp> event;
set<int> line;
for(int i=0; i<n; i++){
pi p1 = a[i];
pi p2 = a[(i+1)%n];
if(p1.second == p2.second) continue;
if(p1.second > p2.second) swap(p1, p2);
event.push_back({p1.second, p1.first, 1});
event.push_back({p2.second, p1.first, -1});
}
sort(event.begin(), event.end());
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) line.insert(event[e].xc);
else line.erase(event[e].xc);
e++;
}
if(line.empty()){
i = e;
continue;
}
auto it1 = line.begin(), it2 = ++line.begin();
int sy = event[i].yc, ey = event[e].yc;
while(it2 != line.end()){
vector<pi> tmp, split1, split2;
cut_polygon(a, split1, tmp, *it1, *it2, sy);
tmp.clear();
cut_polygon(a, tmp, split2, *it1, *it2, ey);
tmp.clear();
lint area1 = abs(get_area(split1));
lint area2 = abs(get_area(split2));
if(abs(area2 - area1) % (2 * *it2 - 2 * *it1) == 0){
lint dx = (area2 - area1) / (2 * *it2 - 2 * *it1);
lint dx2 = ey - sy;
if(abs(dx) % 2 == dx2 % 2){
lint q = (dx2 + dx) / 2;
split1.clear();
split2.clear();
if(sy + q >= sy && sy + q < ey){
cut_polygon(a, split1, split2, *it1, *it2, sy + q);
if(non_enclosing(*it1, *it2, sy + q) && hapdong(split1, split2)){
save_results(*it1, *it2, sy+q);
return;
}
}
}
}
it1++;
it1++;
if(it1 == line.end()) break;
it2++;
it2++;
}
i = e;
}
}
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++){
if(n > 2000) point12();
else 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:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=2; i<v.size(); i++){
^
demarcation.cpp: In function 'void debug(std::vector<std::pair<int, int> >&)':
demarcation.cpp:97:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
printf("%d ", v.size());
^
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:120: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:197:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<event.size(); ){
^
demarcation.cpp:199:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(e < event.size() && event[e].yc == event[i].yc){
^
demarcation.cpp: In function 'int main()':
demarcation.cpp:278:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
demarcation.cpp:281:43: 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 |
Correct |
26 ms |
2460 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
2036 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
2460 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
2036 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
