poj 2296 Map Labeler

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分 + 2-sat判定

题意：平面上有n个点，每个点有一个属于自己的区域，这个区域一定是一个正方形，另外这个区域一定出现在点的正上方或正下方，在正上方时，点在正方形下边的中点；在正下方时，点在正方形上边的中点。你可以把每个点对应的区域放在上方或下方，但是要令所有的点的区域不能相交（如果只是公用了边，不算相交）。在满足不想交的情况下，令区域最大（即正方形边长最大）

因为顶点坐标范围给出了，所以我们是可以知道正方形的大小范围的，用二分去枚举正方形的大小，看看在当前的大小下，能不能满足所有区域都不想交，能满足的话，说明是个可行解，那么就试着增大正方形的大小，看看还是否能满足，所以向上二分。如果当前不能满足的时候说明正方形太大了，那么就向下二分

至于怎么判断是否所有区域可以不想交，就是使用2-sat来判断的

一个点的区域可上可下，这很符合2-sat的模型，所以对于一个顶点，区域在上方和在下方用a,~a来表示

在判断之前我先对所有点进行了一次纵坐标的升序排序（横坐标不用排），这个排序并不是必须的，但是我排了序，更方便处理一些

下面看看怎么构图

枚举图中任意两点u，v，设当前二分枚举出来的正方形边长为s，因为排序了，所以约定yv >= yx

两点的区域能相交的一个条件就是他们的水平距离要小于s，即abs(xu-xv) < s，否则就是高度如何，都是不会相交的。所以两点满足abs(xu-xv) < s后，我们在进一步判断

  1. yv = yu , 这个时候，u和v的区域必须一上一下，否则必然相交，所以可以找到必然关系

    u->~v , ~u->v , v->~u , ~v->u

  2. 0 < yv - yu <= s , 这时候其实可以知道，只有当u的区域在下方，v的区域在上方时，他们才不会出现相交，否则其他任何摆放都会出现相交，所以这是个固定操作，固定u摆下方v摆上方

    u->~u , ~v->v

  3. s < yv - yu <= 2s , 当u放上方，v放下方的时候才会发生相交（其他情况不会），这是一对矛盾关系，可以推出必然关系，就是u在上方时v必在上方，v在下方时u必在下方

    u->v , ~v->~u

  4. 2s < yv - yx，这样不会出现矛盾关系，结束了

每次二分答案后，就利用s来构一次图，然后进行判定即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/*
构图时，思维要严谨，考虑各种情况
事先排序，有助于分类讨论
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define N 110
#define MAX 100000 //10000
#define cl memset
#define pb push_back

int n;
vector<int>e[2*N];
struct point{
	int x,y;
	bool operator<(point a)const{
		return y < a.y;
	}
}p[N];
int dcnt,bcnt,top,dfn[2*N],low[2*N],belong[2*N],stack[2*N];
bool ins[2*N];

inline int abs(int val){
	return val > 0 ? val : -val;
}

inline void add(int u,int v){
	e[u].pb(v);
}

void tarjan(int u){
	dfn[u] = low[u] = ++dcnt;
	stack[++top] = u; ins[u] = true;
	for(int i = 0; i < e[u].size(); i++){
		int v = e[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(ins[v])
			low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u] == low[u]){
		++bcnt;
		while(true){
			int x = stack[top--];
			ins[x] = false; 
			belong[x] = bcnt;
			if(x == u) break;
		}
	}
}

void build(int s){
	for(int i = 0; i < 2*n; i++)
		e[i].clear();
	for(int u = 0; u < n; u++)
		for(int v = u+1; v < n; v++)
			if(abs(p[u].x - p[v].x) < s){
				if(p[v].y == p[u].y){ //两者高度相等
					add(u<<1,v<<1|1); add(u<<1|1,v<<1);
					add(v<<1,u<<1|1); add(v<<1|1,u<<1);
				}
				else if(p[v].y - p[u].y < s){
					//u一定不能放上面，否则将导致v一定不能放
					//换言之u一定要放下面，所以先固定u
					//v也一定不能放下面，否则将导则u不能放
					//换言之v一定要放上面，所以也固定v
					add(u<<1,u<<1|1); //固定u在下面
					add(v<<1|1,v<<1); //固定v在上面
				}
				else if(p[v].y - p[u].y < 2*s){
					add(u<<1,v<<1); 
					add(v<<1|1,u<<1|1);
				}
			}
}

bool check(){
	dcnt = bcnt = top = 0;
	cl(dfn,0,sizeof(dfn));
	cl(ins,false,sizeof(ins));
	for(int i = 0; i < 2*n; i++)
		if(!dfn[i])
			tarjan(i);
	for(int i = 0; i < n; i++)
		if(belong[i<<1] == belong[i<<1|1])
			return false;
	return true;
}

int main(){
	int cas;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&n);
		for(int i = 0; i < n; i++)
			scanf("%d%d",&p[i].x,&p[i].y);
		sort(p,p+n);

		int low = 0 , high = MAX , ans = 0;
		while(low <= high){
			int mid = (low + high) >> 1;
			build(mid);
			if(check()){
				low = mid + 1; ans = mid;
			}
			else high = mid - 1;
		}
		printf("%d\n",ans);
	}
	return 0;
}