oj.uz

Submission #107471

# Submission time Handle Problem Language Result Execution time Memory
107471 2019-04-24T16:46:23 Z gs14004 Demarcation (BOI14_demarcation) C++17
50 / 100
 258 ms 5500 KB 
#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++) gph[i].clear();
	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<rect_list.size(); 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);
				}
			}
			break;
		}
	}
}

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());
		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: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++) gph[i].clear();
               ~^~~~~~~~~~~~~~~~~
demarcation.cpp:269:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<rect_list.size(); i++){
               ~^~~~~~~~~~~~~~~~~
demarcation.cpp:280: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:340:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
demarcation.cpp:343: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3040 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 17 ms 3156 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 5 ms 2688 KB Output is correct
8 Correct 5 ms 2688 KB Output is correct
9 Correct 258 ms 5484 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 ms 2688 KB Output is correct
12 Correct 4 ms 2688 KB Output is correct
13 Correct 4 ms 2688 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 5 ms 2748 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 5 ms 2688 KB Output is correct
10 Correct 5 ms 2688 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 4 ms 2688 KB Output is correct
13 Correct 5 ms 2736 KB Output is correct
14 Correct 5 ms 2688 KB Output is correct
15 Correct 5 ms 2688 KB Output is correct
16 Correct 5 ms 2688 KB Output is correct
17 Correct 5 ms 2688 KB Output is correct
18 Correct 6 ms 2688 KB Output is correct
19 Correct 4 ms 2688 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 5 ms 2688 KB Output is correct
22 Correct 6 ms 2688 KB Output is correct
23 Correct 5 ms 2688 KB Output is correct
24 Correct 5 ms 2688 KB Output is correct
25 Correct 4 ms 2688 KB Output is correct
26 Correct 4 ms 2688 KB Output is correct
27 Correct 3 ms 2688 KB Output is correct
28 Correct 5 ms 2688 KB Output is correct
29 Correct 4 ms 2688 KB Output is correct
30 Correct 5 ms 2688 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 5 ms 2688 KB Output is correct
8 Correct 6 ms 2660 KB Output is correct
9 Correct 5 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 ms 2688 KB Output is correct
12 Correct 5 ms 2688 KB Output is correct
13 Correct 5 ms 2688 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 4 ms 2688 KB Output is correct
16 Correct 4 ms 2688 KB Output is correct
17 Correct 5 ms 2688 KB Output is correct
18 Correct 5 ms 2688 KB Output is correct
19 Correct 5 ms 2688 KB Output is correct
20 Correct 18 ms 2688 KB Output is correct
21 Correct 5 ms 2688 KB Output is correct
22 Correct 6 ms 2688 KB Output is correct
23 Correct 5 ms 2688 KB Output is correct
24 Correct 4 ms 2688 KB Output is correct
25 Correct 5 ms 2688 KB Output is correct
26 Correct 4 ms 2688 KB Output is correct
27 Correct 4 ms 2684 KB Output is correct
28 Correct 5 ms 2688 KB Output is correct
29 Correct 5 ms 2688 KB Output is correct
30 Correct 5 ms 2688 KB Output is correct
31 Correct 5 ms 2688 KB Output is correct
32 Correct 8 ms 2944 KB Output is correct
33 Correct 7 ms 2816 KB Output is correct
34 Correct 8 ms 2816 KB Output is correct
35 Correct 7 ms 2816 KB Output is correct
36 Correct 8 ms 2816 KB Output is correct
37 Correct 8 ms 2864 KB Output is correct
38 Correct 10 ms 2944 KB Output is correct
39 Correct 6 ms 2688 KB Output is correct

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3072 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 18 ms 3116 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2688 KB Output is correct
8 Correct 5 ms 2688 KB Output is correct
9 Correct 255 ms 5500 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 5 ms 2688 KB Output is correct
13 Correct 5 ms 2688 KB Output is correct
14 Correct 5 ms 2688 KB Output is correct
15 Correct 5 ms 2688 KB Output is correct
16 Correct 5 ms 2688 KB Output is correct
17 Correct 6 ms 2688 KB Output is correct
18 Correct 5 ms 2688 KB Output is correct
19 Correct 5 ms 2688 KB Output is correct
20 Correct 5 ms 2688 KB Output is correct
21 Correct 5 ms 2688 KB Output is correct
22 Correct 5 ms 2688 KB Output is correct
23 Correct 5 ms 2688 KB Output is correct
24 Correct 3 ms 2688 KB Output is correct
25 Correct 5 ms 2688 KB Output is correct
26 Correct 4 ms 2688 KB Output is correct
27 Correct 5 ms 2688 KB Output is correct
28 Correct 4 ms 2688 KB Output is correct
29 Correct 4 ms 2688 KB Output is correct
30 Correct 5 ms 2724 KB Output is correct
31 Correct 5 ms 2688 KB Output is correct
32 Correct 4 ms 2688 KB Output is correct
33 Correct 4 ms 2688 KB Output is correct
34 Correct 5 ms 2688 KB Output is correct
35 Correct 11 ms 2944 KB Output is correct
36 Correct 7 ms 2944 KB Output is correct
37 Correct 11 ms 2816 KB Output is correct
38 Correct 8 ms 2816 KB Output is correct
39 Correct 8 ms 2816 KB Output is correct
40 Correct 9 ms 2944 KB Output is correct
41 Correct 11 ms 2944 KB Output is correct
42 Correct 6 ms 2816 KB Output is correct
43 Incorrect 12 ms 2816 KB Output isn't correct
44 Halted 0 ms 0 KB -