Submission #12869

#	Time	Username	Problem	Language	Result	Execution time	Memory
12869		ainta	Demarcation (BOI14_demarcation)	C++98	100 / 100	126 ms	19140 KiB

demarcation

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<set>
#define INF 1111111111
using namespace std;
#define SIT set<A>::iterator
int n, cnt, chk, m;
vector<int>E[101000];

struct Rect{
	int x1, x2, y1, y2;
	long long S;
}R[101000];

struct A{
	int y1, y2, x;
	bool operator<(const A &p)const{
		return y2 != p.y2 ? y2 < p.y2 : y1 < p.y1;
	}
};

struct Seg{
	int x, y1, y2;
	bool operator<(const Seg &p)const{
		return x < p.x;
	}
}w[101000];

struct point{
	int x, y;
}P[101000], P1[101000], P2[101000];

void Make_Seg(){
	int i;
	m = 0;
	for (i = 0; i < n; i++){
		if (P[i].x == P[i + 1].x){
			w[m].x = P[i].x;
			w[m].y1 = min(P[i].y, P[i + 1].y);
			w[m].y2 = max(P[i].y, P[i + 1].y);
			m++;
		}
	}
	sort(w, w + m);
}

set<A> Set;

void Make(int x1, int x2, int y1, int y2){
	if (x1 == x2)return;
	cnt++;
	R[cnt].x1 = x1, R[cnt].x2 = x2, R[cnt].y1 = y1, R[cnt].y2 = y2;
	R[cnt].S = (long long)(y2 - y1)*(x2 - x1);
}

void Ins(int x, int y1, int y2){
	A tp; tp.x = x, tp.y1 = y1, tp.y2 = y2;
	Set.insert(tp);
}

void Del(SIT it, Seg s){
	int x = it->x, y1 = it->y1, y2 = it->y2;
	Set.erase(it);
	Make(x, s.x, y1, y2);
	if (s.y1 != y1){
		Ins(s.x, y1, s.y1);
	}
	if (s.y2 != y2){
		Ins(s.x, s.y2, y2);
	}
}

void Make_Rect(){
	int i, y1, y2, ck;
	A tp;
	SIT it, it2;
	cnt = 0;
	for (i = 0; i < m; i++){
		tp.x = 0, tp.y1 = -1, tp.y2 = w[i].y2;
		it = Set.lower_bound(tp);
		if (it != Set.end() && it->y1 <= w[i].y1){
			Del(it, w[i]);
			continue;
		}
		y1 = w[i].y1, y2 = w[i].y2;
		ck = 0;
		if (it != Set.end() && it->y1 == w[i].y2){
			y2 = it->y2;
			Make(it->x, w[i].x, it->y1, it->y2);
			ck += 1;
		}
		if (it != Set.begin()){
			it2 = it; it2--;
			if (it2->y2 == w[i].y1){
				y1 = it2->y1;
				Make(it2->x, w[i].x, it2->y1, it2->y2);
				ck += 2;
			}
		}
		if (ck & 1)Set.erase(it);
		if (ck & 2)Set.erase(it2);
		Ins(w[i].x, y1, y2);
	}
	Set.clear();
}

void Make_Tree(){
	int i, ck;
	A tp;
	SIT it, it2, it3;
	for (i = 1; i <= cnt; i++){
		tp.x = 0, tp.y2 = R[i].y2, tp.y1 = -1;
		it = Set.lower_bound(tp);
		ck = 0;
		if (it != Set.begin()){
			it2 = it; it2--;
			while (1){
				if (it2->y2 <= R[i].y1)break;
				if (R[it2->x].x2 == R[i].x1){
					E[it2->x].push_back(i);
					E[i].push_back(it2->x);
				}
				if (it2 != Set.begin()){
					it3 = it2; it3--;
				}
				else ck = 1;
				if (it2->y1 < R[i].y1){
					Ins(it2->x, it2->y1, R[i].y1);
				}
				Set.erase(it2);
				if (!ck)it2 = it3;
				else break;
			}
		}
		if(it != Set.end() && it->y1 < R[i].y2){
			if (R[it->x].x2 == R[i].x1){
				E[it->x].push_back(i);
				E[i].push_back(it->x);
			}
			if (it->y1 < R[i].y1){
				Ins(it->x, it->y1, R[i].y1);
			}
			if (it->y2 > R[i].y2){
				Ins(it->x, R[i].y2, it->y2);
			}
			Set.erase(it);
		}
		Ins(i, R[i].y1, R[i].y2);
	}
	Set.clear();
}
long long D[101000];
bool On(point a, point b, int x, int y){
	if (a.x == x && b.x == x){
		if (min(b.y, a.y) <= y && y <= max(b.y, a.y))return true;
	}
	else if (a.y == y && b.y == y){
		if (min(b.x, a.x) <= x && x <= max(b.x, a.x))return true;
	}
	return false;
}
bool On2(int a, int x, int y){
	a %= n;
	int b = (a + n - 1) % n;
	return On(P[a], P[b], x, y);
}
int c1, c2;
bool Deleted[101000];
void Cut_Poly(int x, int y1, int y2){
	int i, t, pv1, pv2, cc = 0;
	c1 = 0;
	for (i = 0; i <= n; i++){
		if (P[i].x == x && P[i].y == y1)break;
		if (i && On2(i, x, y1))break;
	}
	if (x != P[i].x || y1 != P[i].y){
		P1[c1].x = x, P1[c1].y = y1; c1++;
	}
	t = i%n;
	while (1){
		P1[c1].x = P[t].x, P1[c1].y = P[t].y; c1++;
		t = (t + 1) % n;
		if (On2(t, x, y2))break;
	}
	P1[c1].x = x, P1[c1].y = y2; c1++;
	for (i = 0; i < c1; i++){
		pv1 = (i + c1 - 1) % c1;
		pv2 = (i + 1) % c1;
		Deleted[i] = false;
		if (On(P1[pv1], P1[pv2], P1[i].x, P1[i].y))Deleted[i] = true;
	}
	for (i = 0; i < c1; i++){
		if (!Deleted[i])P1[cc++] = P1[i];
	}
	c1 = cc;
}
void Rotate(){
	int i, t;
	for (i = 0; i < c1; i++){
		t = P1[i].x;
		P1[i].x = P1[i].y;
		P1[i].y = -t;
	}
}
bool Match(){
	int i, x, y, j, Mx = INF, My = INF, t1, t2;
	for (i = 0; i < c1; i++){
		if (Mx > P1[i].x || (Mx == P1[i].x && My > P1[i].y)){
			Mx = P1[i].x, My = P1[i].y, t1 = i;
		}
	}
	Mx = My = INF;
	for (i = 0; i < c1; i++){
		if (Mx > P2[i].x || (Mx == P2[i].x && My > P2[i].y)){
			Mx = P2[i].x, My = P2[i].y, t2 = i;
		}
	}
	Mx = P1[t1].x - P2[t2].x, My = P1[t1].y - P2[t2].y;
	for (i = 0; i < c1; i++){
		if (P1[(t1 + i) % c1].x - P2[(t2 + i) % c1].x != Mx)break;
		if (P1[(t1 + i) % c1].y - P2[(t2 + i) % c1].y != My)break;
	}
	if (i == c1)return true;
	for (i = 0; i < c1; i++){
		if (P1[(t1 + i) % c1].x - P2[(t2 + c1 - i) % c1].x != Mx)break;
		if (P1[(t1 + i) % c1].y - P2[(t2 + c1 - i) % c1].y != My)break;
	}
	return i == c1;
}
bool Same(){
	int i;
	if (c1 != c2)return false;
	if (Match())return true;
	for (i = 0; i < 3; i++){
		Rotate();
		if (Match())return true;
	}
	for (i = 0; i < c1; i++)P1[i].x = -P1[i].x;
	if (Match())return true;
	for (i = 0; i < 3; i++){
		Rotate();
		if (Match())return true;
	}
	return false;
}
bool Check(int x, int y1, int y2){
	int i;
	Cut_Poly(x, y1, y2);
	for (i = 0; i < c1; i++)P2[i] = P1[i];
	c2 = c1;
	Cut_Poly(x, y2, y1);
	if (!Same())return false;
	if (!chk)printf("%d %d %d %d", x, y1, x, y2);
	else printf("%d %d %d %d", y1, x, y2, x);
	return true;
}
void DFS(int a, int pp){
	int i, x;
	D[a] = R[a].S;
	for (i = 0; i < E[a].size(); i++){
		x = E[a][i];
		if (x == pp)continue;
		DFS(E[a][i], a);
		D[a] += D[E[a][i]];
	}
}


bool DP(int a, int pp){
	int i, x;
	long long t, S1 = 0, S2 = 0, M, y;
	if (pp){
		M = D[pp];
		D[pp] -= D[a];
		D[a] = M;
	}
	else M = D[a];
	for (i = 0; i < E[a].size(); i++){
		x = E[a][i];
		if (R[x].x1 < R[a].x1){
			if (D[x] * 2 == M){
				if (Check(R[x].x2, max(R[x].y1, R[a].y1), min(R[x].y2, R[a].y2)))return true;
			}
			S1 += D[x];
		}
		else{
			if (D[x] * 2 == M){
				if (Check(R[x].x1, max(R[x].y1, R[a].y1), min(R[x].y2, R[a].y2)))return true;
			}
			S2 += D[x];
		}
	}
	t = S2 - S1 + R[a].S;
	y = R[a].y2 - R[a].y1;
	if (t >= 0 && t % (2 * y) == 0){
		t = t / (2 * y);
		if (t <= R[a].x2 - R[a].x1){
			if (Check(R[a].x1 + t, R[a].y1, R[a].y2))return true;
		}
	}
	for (i = 0; i < E[a].size(); i++){
		if (E[a][i] != pp){
			if (DP(E[a][i], a))return true;
		}
	}
	D[a] = D[a] - D[pp];
	D[pp] = M;
	return false;
}

bool Dynamic(){
	int i;
	DFS(1, 0);
	return DP(1, 0);
}

void init(){
	int i;
	for (i = 1; i <= cnt; i++){
		E[i].clear();
	}
}

bool Pos(){
	Make_Seg();
	Make_Rect();
	Make_Tree();
	if (Dynamic())return true;
	init();
	return false;
}

int main(){
	//freopen("input.txt", "r", stdin);
	int i;
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%d%d", &P[i].x, &P[i].y);
	}
	P[n] = P[0];
	if (Pos()){
		return 0;
	}
	for (i = 0; i <= n; i++)swap(P[i].x, P[i].y);
	chk = 1;
	if (Pos()){
		return 0;
	}
	printf("NO\n");
}

Compilation message (stderr)

demarcation.cpp: In function 'bool Match()':
demarcation.cpp:207:9: warning: unused variable 'x' [-Wunused-variable]
  int i, x, y, j, Mx = INF, My = INF, t1, t2;
         ^
demarcation.cpp:207:12: warning: unused variable 'y' [-Wunused-variable]
  int i, x, y, j, Mx = INF, My = INF, t1, t2;
            ^
demarcation.cpp:207:15: warning: unused variable 'j' [-Wunused-variable]
  int i, x, y, j, Mx = INF, My = INF, t1, t2;
               ^
demarcation.cpp: In function 'void DFS(int, int)':
demarcation.cpp:261:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
                ^
demarcation.cpp: In function 'bool DP(int, int)':
demarcation.cpp:279:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
                ^
demarcation.cpp:302:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
                ^
demarcation.cpp: In function 'bool Dynamic()':
demarcation.cpp:313:6: warning: unused variable 'i' [-Wunused-variable]
  int i;
      ^
demarcation.cpp: In function 'int main()':
demarcation.cpp:337:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
demarcation.cpp:339:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &P[i].x, &P[i].y);
                                  ^
demarcation.cpp: In function 'bool Match()':
demarcation.cpp:219:25: warning: 't2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Mx = P1[t1].x - P2[t2].x, My = P1[t1].y - P2[t2].y;
                         ^
demarcation.cpp:219:14: warning: 't1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Mx = P1[t1].x - P2[t2].x, My = P1[t1].y - P2[t2].y;
              ^

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