Hdu 3622(二分+2-SAT)

Hdu 3622
二分后2-SAT判断
1、2-SAT加边视情况加
2、浮点数二分查找的写法
3、浮点数的eps最好开多一点,防卡精度

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
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#define ll long long
#define db double
#define ms(i,j) memset(i,j)
#define INF 100000000
#define llINF 1LL<<60
using namespace std;
const int MAXN = (100 + 5) * 2;
struct TwoSat
{
int mark[MAXN*2];
int S[MAXN*2];
vector<int> G[MAXN*2];
int n, c;
int init(int ni)
{
n = ni;
for (int i=0;i<=n*2;i++)
{
mark[i] = false;
G[i].clear();
}
}
int dfs(int u)
{
if (mark[u^1]) return false;
if (mark[u]) return true;
mark[u] = true;
S[++c] = u;
for (int i=0;i<G[u].size();i++)
{
if (!dfs(G[u][i])) return false;
}
return true;
}
int solve()
{
for (int i=0;i<n*2;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 n;
int xi[MAXN], yi[MAXN];
db dis(int x, int y)
{
return sqrt(1.0*(xi[x]-xi[y])*(xi[x]-xi[y]) + (yi[x]-yi[y])*(yi[x]-yi[y]));
}
int init()
{
for (int i=0;i<n;i++)
{
scanf("%d%d%d%d", &xi[i], &yi[i], &xi[i+n], &yi[i+n]);
}
}
int solve()
{
db l = 0.0, r = 40000.0;
db ans = 0;
for (int i=0;i<100;i++)
{
db mid = (l+r)/2.0;
ts.init(n);
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
{
int x = i*2, y = j*2;
if (dis(i,j)+0.0000001<mid*2)
{
ts.G[x].push_back(y^1);
ts.G[y].push_back(x^1);
}
if (dis(i,j+n)+0.0000001<mid*2)
{
ts.G[x].push_back(y);
ts.G[y^1].push_back(x^1);
}
if (dis(i+n,j)+0.0000001<mid*2)
{
ts.G[x^1].push_back(y^1);
ts.G[y].push_back(x);
}
if (dis(i+n,j+n)+0.0000001<mid*2)
{
ts.G[x^1].push_back(y);
ts.G[y^1].push_back(x);
}
}
if (ts.solve())
{
ans = l = mid;
} else r = mid;
}
printf("%.2f\n", ans);
}
int main()
{
while (scanf("%d", &n)==1)
{
init();
solve();
}
return 0;
}

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