算法：HDU 3622 Bomb Game（2-SAT + 二分）

算法：HDU 3622 Bomb Game（2-SAT + 二分）2014-01-07 csdn shuangde800【题目大意】

要在坐标轴上放N次炸弹，每次可以选择两个位置中的一个位置放置，每个炸弹都可以控制它的爆炸范围（以放置位置为圆心的半径为r的圆圈），问半径最大可以多少，使得任意两个炸弹的爆炸范围都不重合。

【思路】

类似与poj 2296 ，但是判断重合的方法容易多了，果断 1Y

注意精度问题。

【代码】

#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<vector>#include<cmath>#define SQ（x） （（x）*（x））using namespace std; const int MAXN = 110;const int VN = MAXN*2;const int EN = VN*VN*2;const int INF= 0x3f3f3f3f;const double eps = 1e-9;int n;vector<int>g[VN]; struct Node{int x, y;void input（）{scanf（"%d%d",&x,&y）;}}arr[MAXN][2]; void init（）{for（int i=0; i<2*n; ++i）g[i].clear（）;}void addEdge（int u, int v）{g[u].push_back（v）;} class Two_Sat{public:bool check（）{scc（）; for（int i=0; i<n; ++i）if（belong[i] == belong[i+n]）return false;return true;}private:void tarjan（const int u）{int v;low[u] = dfn[u] = ++idx;sta[top++] = u;instack[u] = true;for（int i=0; i<g[u].size（）; ++i）{v = g[u][i];if（dfn[v] == -1）{tarjan（v）;low[u] = min（low[u], low[v]）;}else if（instack[v]）{low[u] = min（low[u], dfn[v]）;}}if（low[u] == dfn[u]）{++bcnt;do{v = sta[--top];instack[v] = false;belong[v] = bcnt;}while（u ！= v）;}}void scc（）{idx=top=bcnt=0;memset（instack, 0, sizeof（instack））;memset（dfn, -1, sizeof（dfn））;for（int i=0; i<2*n; ++i）if（dfn[i] == -1）tarjan（i）;}private:int idx, top, bcnt;int low[VN], dfn[VN], belong[VN], sta[VN];bool instack[VN];}sat;double getDist（Node& a, Node& b）{returnsqrt（SQ（a.x*1.0-b.x）+SQ（a.y*1.0-b.y））;} void buildGraph（double r）{init（）;for（int i=0; i<n; ++i）{for（int j=i+1; j<n; ++j）{if（2*r - getDist（arr[i][0], arr[j][0]） > eps） { //上， 上addEdge（i, j+n）;addEdge（j, i+n）;}if（2*r - getDist（arr[i][0], arr[j][1]） > eps） { //上， 下addEdge（i, j）;addEdge（j+n, i+n）;}if（2*r - getDist（arr[i][1], arr[j][0]） > eps）{ // 下，上addEdge（i+n, j+n）;addEdge（j, i）;}if（2*r - getDist（arr[i][1], arr[j][1]） > eps）{ // 下，下addEdge（i+n, j）;addEdge（j+n, i）;}}}} int main（）{ while（~scanf（"%d", &n））{ for（int i=0; i<n; ++i）{arr[i][0].input（）;arr[i][1].input（）;} double l=0, r=20000, m, ans; while（r - l > eps）{m = （r+l）/2.0;// 建图buildGraph（m）;if（sat.check（））{l = m+eps;ans = m;}else r=m;} printf（"%.2f
", ans）;}return 0;}