一个很玄乎的问题，但听到2-SAT之后就豁然开朗了。题目的意思是这样的，给你n个点群，每个点群里面有两个点，你要在每个点群里面选一个点，以这些点做半径为r的圆，然后r会有一个最大值，问的就是怎么选这些点使得r最大。
2-SAT就是对于每个变量有一些制约的关系 a->b 表示选了a就就要选b。然后我们二分这个半径，对于两点间距离<2*r的点（a,b）选了a就不能选b,选了b就不能选a，以此构图。然后跑一次强连通分量。最后判是否有解的时候就是判对于两个属于相同点群的点，它们不能处于同一强连通分量下。写的时候跪的点实在太多了，数组越界呀，强连通写错呀，精度呀，这样的题太坑爹了－ －0
|
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 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<vector>#define ll long long#define maxn 220#define eps 1e-8using
namespace std;struct
Point{ double
x, y, z; Point(double
xi, double
yi, double
zi) :x(xi), y(yi), z(zi){} Point(){}}p[maxn * 2];double
dist(Point a, Point b){ return
sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) + (a.z - b.z)*(a.z - b.z));}double
dis[maxn * 2][maxn * 2];int
low[maxn * 2];int
pre[maxn * 2];int
dfs_clock;int
sta[maxn * 2];int
st;int
sccno[maxn * 2];int
n;vector<int> G[maxn * 2];int
scc_cnt;int
dcmp(double
x){ return
(x > eps) - (x < -eps);}void
dfs(int
u){ low[u] = pre[u] = ++dfs_clock; sta[++st] = u; for
(int i = 0; i < G[u].size(); i++){ int
v = G[u][i]; if
(!pre[v]){ dfs(v); low[u] = min(low[u], low[v]); } else
if (!sccno[v]){ low[u] = min(low[u], pre[v]); } } if
(low[u] == pre[u]){ ++scc_cnt; while
(1){ int
x = sta[st]; st--; sccno[x] = scc_cnt; if
(x == u) break; } }}bool
judge(double
x){ memset(sccno, 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); memset(low, 0, sizeof(low)); st = 0; dfs_clock = 0; scc_cnt = 0; for
(int i = 0; i <= 2 * n; i++) G[i].clear(); for
(int i = 0; i < n; i++){ for
(int j = i + 1; j < n; j++){ if
(dcmp(dis[i][j] - 2 * x) < 0){ G[i].push_back(j + n); G[j].push_back(i + n); } if
(dcmp(dis[i][j + n] - 2 * x) < 0){ G[i].push_back(j); G[j + n].push_back(i + n); } if
(dcmp(dis[i + n][j] - 2 * x) < 0){ G[i + n].push_back(j + n); G[j].push_back(i); } if
(dcmp(dis[i + n][j + n] - 2 * x) < 0){ G[i + n].push_back(j); G[j + n].push_back(i); } } } for
(int i = 0; i < 2 * n; i++){ if
(!pre[i]) dfs(i); } for
(int i = 0; i < n; i++){ if
(sccno[i] == sccno[i + n]) return
false; } return
true;}int
main(){ while
(cin >> n) { for
(int i = 0; i < n; i++){ scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z); scanf("%lf%lf%lf", &p[i + n].x, &p[i + n].y, &p[i + n].z); } for
(int i = 0; i < 2 * n; i++){ for
(int j = i + 1; j < 2 * n; j++){ dis[i][j] = dis[j][i] = dist(p[i], p[j]); } } double
l = 0, r = 1e10; while
(dcmp(r - l)>0){ double
mid = (l + r) / 2; if
(judge(mid)) l = mid; else
r = mid; } int
tmp = l * 1000; double
ans = tmp / 1000.0; printf("%.3lf\n", ans); } return
0;} |
ZOJ3717 Balloon(2-SAT),布布扣,bubuko.com
原文：http://www.cnblogs.com/chanme/p/3634880.html