[2-sat]HDOJ3622 Bomb Game

题意：给n对炸弹，每对炸弹选其中一个爆炸。

每个炸弹爆炸的半径相同 圆不能相交， 求最大半径

2-sat简介

二分半径， 枚举n*2个炸弹

若i炸弹与j炸弹的距离小于半径*2 则建边

比如  第一对炸弹的第一个 与 第二对炸弹的第一个 距离小于半径*2

　　  则 建立 第一对炸弹的第一个$\Rightarrow $第二对炸弹的第二个 、第二对炸弹的第一个$\Rightarrow $第一对炸弹的第二个

然后 通过判断能否取到n个炸弹 来判断 能否取该半径

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 typedef pair<double, double> PI;

 const double eps=1e-;

 #define INF 0x3f3f3f3f

 const int N=*;

 const int M=N*N;

 //注意n是拆点后的大小 即 n <<= 1 N为点数(注意要翻倍) M为边数 i&1=0为i真 i&1=1为i假

 struct Edge

 {

     int to, nex;

 }edge[M];

 //注意 N M 要修改

 int head[N], edgenum;

 void addedge(int u, int v)

 {

     Edge E={v, head[u]};

     edge[edgenum]=E;

     head[u]=edgenum++;

 }

 bool mark[N];

 int Stack[N], top;

 void init()

 {

     memset(head, -, sizeof(head));

     edgenum=;

     memset(mark, , sizeof(mark));

 }

 bool dfs(int x)

 {

     if(mark[x^])

         return false;//一定是拆点的点先判断

     if(mark[x])

         return true;

     mark[x]=true;

     Stack[top++]=x;

     for(int i=head[x];i!=-;i=edge[i].nex)

         if(!dfs(edge[i].to))

             return false;

     return true;

 }

 bool solve(int n)

 {

     for(int i=;i<n;i+=)

         if(!mark[i] && !mark[i^])

         {

             top=;

             if(!dfs(i))

             {

                 while(top)

                     mark[Stack[--top]]=false;

                 if(!dfs(i^))

                     return false;

             }

         }

     return true;

 }

 PI a[];

 double dis(PI a, PI b)

 {

     return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));

 }

 int main()

 {

     int n;

     while(~scanf("%d", &n))

     {

         for(int i=;i<n;i++)

         {

             double x1, y1, x2, y2;

             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

             a[i*]=make_pair(x1, y1);

             a[i*+]=make_pair(x2, y2);

         }

         double l=, r=;

         while(r-l>=eps)

         {

             double m=(l+r)/2.0;

             init();

             for(int i=;i<n*;i++)

                 for(int j=i++!(i&);j<*n;j++)

                     if(dis(a[i], a[j])<*m)

                     {

                         addedge(i, j^);

                         addedge(j, i^);

                     }

             if(solve(n*))

                 l=m;

             else

                 r=m;

         }

         printf("%.2f\n", r);

     }

     return ;

 }

HDOJ 3622