poj 2296(二分+2-SAT)

poj 2296
教训:
1、注意复杂情况的分类讨论
2、$a<x<b$这样的不要写错了

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
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ms(i,j) memset(i, j, sizeof i);
const int MAXM = 1000 + 5;
struct TwoSAT
{
vector<int> G[MAXM*2];
int S[MAXM*2];
bool mark[MAXM*2];
int n, c;
void init(int n)
{
this->n = n;
for (int i=0;i<=2*n;i++)
{
G[i].clear();
mark[i] = false;
}
}
void ins(int u, int v)
{
G[u].push_back(v);
}
int dfs(int x)
{
if (mark[x^1]) return false;
if (mark[x]) return true;
mark[x] = true;
S[++c] = x;
for (int i=0;i<G[x].size();i++)
{
if (!dfs(G[x][i])) return false;
}
return true;
}
int solve()
{
for (int i=0;i<2*n;i+=2)
if (!mark[i]&&!mark[i+1])
{
c = 0;
if (!dfs(i))
{
while (c>0) mark[S[c--]] = false;
if (!dfs(i+1)) return false;
}
}
return true;
}
}ts;
int m, xi[MAXM], yi[MAXM];
int abss(int x) {return (x<0) ? (-x) : (x);}
void init()
{
scanf("%d", &m);
for (int i=0;i<m;i++)
{
scanf("%d%d", &xi[i], &yi[i]);
}
}
void solve()
{
int l = 0, r = 80000, ans = 0;
while (l < r)
{
int mid = (l+r)/2;
ts.init(m);
for (int i=0;i<m;i++)
for (int j=i+1;j<m;j++)
{
int ax = abss(xi[i]-xi[j]);
int ay = abss(yi[i]-yi[j]);
if (ax<mid)//2*i is up, 2*i+1 is down
{
if (ay<mid)
{
if (yi[i]==yi[j])//特判差值为0的情况
{
ts.ins(2*i+1, 2*j);
ts.ins(2*j+1, 2*i);
ts.ins(2*i, 2*j+1);
ts.ins(2*j, 2*i+1);
} else if (yi[i]>yi[j])//A是上面的点,B是下面的点
{
ts.ins(2*i+1, 2*i);
ts.ins(2*j, 2*j+1);
} else//B是上面的点,A是下面的点
{
ts.ins(2*j+1, 2*j);
ts.ins(2*i, 2*i+1);
}
} else if (ay<2*mid)
{
if (yi[i]>yi[j])//A是上面的点,B是下面的点
{
ts.ins(2*i+1, 2*j+1);
ts.ins(2*j, 2*i);
} else//B是上面的点,A是下面的点
{
ts.ins(2*j+1, 2*i+1);
ts.ins(2*i, 2*j);
}
}
}
}
if (ts.solve())
{
ans = mid;
l = mid+1;
}else r = mid;
}
printf("%d\n", ans);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
init();
solve();
}
return 0;
}

------ 本文结束 ------