HDU 3622 Bomb Game
题意：求一个最大半径，使得每一个二元组的点任选一个，能够得到全部圆两两不相交
思路：显然的二分半径，然后2-sat去判定就可以
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std; const int MAXNODE = 105; struct TwoSet {
int n;
vector<int> g[MAXNODE * 2];
bool mark[MAXNODE * 2];
int S[MAXNODE * 2], sn; void init(int tot) {
n = tot * 2;
for (int i = 0; i < n; i += 2) {
g[i].clear();
g[i^1].clear();
}
memset(mark, false, sizeof(mark));
} void add_Edge(int u, int uval, int v, int vval) {
u = u * 2 + uval;
v = v * 2 + vval;
g[u^1].push_back(v);
g[v^1].push_back(u);
} void delete_Edge(int u, int uval, int v, int vval) {
u = u * 2 + uval;
v = v * 2 + vval;
g[u^1].pop_back();
g[v^1].pop_back();
} bool dfs(int u) {
if (mark[u^1]) return false;
if (mark[u]) return true;
mark[u] = true;
S[sn++] = u;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (!dfs(v)) return false;
}
return true;
} bool solve() {
for (int i = 0; i < n; i += 2) {
if (!mark[i] && !mark[i + 1]) {
sn = 0;
if (!dfs(i)){
for (int j = 0; j < sn; j++)
mark[S[j]] = false;
sn = 0;
if (!dfs(i + 1)) return false;
}
}
}
return true;
}
} gao; const int N = 105;
int n; struct Point {
double x, y;
void read() {
scanf("%lf%lf", &x, &y);
}
} p[N][2]; inline double dis(Point a, Point b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
} inline bool xj(Point a, Point b, double r) {
if (dis(a, b) > 2 * r) return false;
return true;
} bool judge(double r) {
gao.init(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
if (xj(p[i][x], p[j][y], r))
gao.add_Edge(i, x, j , y);
}
}
}
}
return gao.solve();
} int main() {
while (~scanf("%d", &n)) {
for (int i = 0; i < n; i++)
for (int j = 0; j < 2; j++)
p[i][j].read();
double l = 0, r = 1e5;
for (int i = 0; i < 30; i++) {
double mid = (l + r) / 2;
if (judge(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n", l);
}
return 0;
}