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;
}