HDU 3622 Bomb Game
题意：求一个最大半径，使得每一个二元组的点任选一个，能够得到全部圆两两不相交
思路：显然的二分半径，然后2-sat去判定就可以
代码：
#include#include #include #include #include #include using namespace std;const int MAXNODE = 105;struct TwoSet { int n; vector 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;}