HDU 3622 Bomb Game

http://acm.hdu.edu.cn/showproblem.php?pid=3622
对半径进行二分，如果冲突则加入边（按照X AND Y == 0的法则插入边），再2-SAT即可。
  1 //#pragma comment(linker, "/STACK:102400000,102400000")
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<string>
  6 #include<cmath>
  7 #include<set>
  8 #include<list>
  9 #include<map>
 10 #include<iterator>
 11 #include<cstdlib>
 12 #include<vector>
 13 #include<queue>
 14 #include<stack>
 15 #include<algorithm>
 16 #include<functional>
 17 using namespace std;
 18 typedef long long LL;
 19 #define ROUND(x) round(x)
 20 #define FLOOR(x) floor(x)
 21 #define CEIL(x) ceil(x)
 22 const int maxn=210;
 23 const int inf=0x3f3f3f3f;
 24 const LL inf64=0x3f3f3f3f3f3f3f3fLL;
 25 const double INF=1e30;
 26 const double eps=1e-6;
 27 int N;
 28 struct Point
 29 {
 30     double x,y;
 31 }p[maxn];
 32 struct TwoSAT
 33 {
 34     int n;
 35     vector<int> G[maxn*2];
 36     bool mark[maxn*2];
 37     int S[maxn*2], c;
 38     bool dfs(int x)
 39     {
 40         if (mark[x^1]) return false;
 41         if (mark[x]) return true;
 42         mark[x] = true;
 43         S[c++] = x;
 44         for (int i = 0; i < G[x].size(); i++)
 45             if (!dfs(G[x][i])) return false;
 46         return true;
 47     }
 48     void init(int n)
 49     {
 50         this->n = n;
 51         for (int i = 0; i < n*2; i++) G[i].clear();
 52         memset(mark, 0, sizeof(mark));
 53     }
 54     void add_and_zero(int x,int y)
 55     {
 56         G[x].push_back(y^1);
 57         G[y].push_back(x^1);
 58     }
 59     bool solve()
 60     {
 61         for(int i = 0; i < n*2; i += 2)
 62             if(!mark[i] && !mark[i+1])
 63             {
 64                 c = 0;
 65                 if(!dfs(i))
 66                 {
 67                     while(c > 0) mark[S[--c]] = false;
 68                     if(!dfs(i+1)) return false;
 69                 }
 70             }
 71         return true;
 72     }
 73 };
 74 TwoSAT sat;
 75 double dist(Point A,Point B)
 76 {
 77     return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
 78 }
 79 void init()
 80 {
 81     sat.init(N);
 82 }
 83 void input()
 84 {
 85     for(int i=0;i<N;i++)
 86         scanf("%lf%lf%lf%lf",&p[2*i].x,&p[2*i].y,&p[2*i+1].x,&p[2*i+1].y);
 87 }
 88 void solve()
 89 {
 90     double L=0.0,R=40000.0;
 91     while(fabs(R-L)>=eps)
 92     {
 93         double M=(L+R)/2;
 94         sat.init(N);
 95         for(int i=0;i<2*N-2;i++)
 96             for(int j=(i%2==0)? i+2:i+1;j<2*N;j++)
 97                 if(dist(p[i],p[j])<M) sat.add_and_zero(i,j);
 98         if(sat.solve()) L=M;
 99         else R=M;
100     }
101     printf("%.2f
",R/2);
102 }
103 int main()
104 {
105 //    freopen("in.cpp","r",stdin);
106     while(~scanf("%d",&N))
107     {
108         init();
109         input();
110         solve();
111     }
112     return 0;
113 }
View Code