제출 #17979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17979		gs14004	경계 (BOI14_demarcation)	C++14	15 / 100	500 ms	2848 KiB

demarcation

#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(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);
		}
	}
	// 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++){
		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");
}

컴파일 시 표준 에러 (stderr) 메시지

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);
                                           ^

• Subtask 1: 0 / 12
• Subtask 2: 15 / 15
• Subtask 3: 0 / 23
• Subtask 4: 0 / 50