HDU3622二分+2-sat

  1 /*HDU3622
  2 这道题是2-sat问题的体型之一，二分答案，2-sat判断是否有自适应的解，从而找到最大的最小值或最小的最大值
  3 这道题有一定的思维上的难度。
  4 二分半径，若不同组的两个点i和j间的距离小于2*rad，则i和j是矛盾点，连上相应的边，求2-sat即可。
  5 
  6 这道题有两种建模的方式：
  7 1、同一组的为一个对象（正好每个对象满足二选一的特点）
  8 2、每个点为一个对象(这种情况下，原来属于同组的两个点就是矛盾点了)
  9 */#include <stdio.h>
 10 #include <stdlib.h>
 11 #include <string.h>
 12 #include <math.h>
 13 #include <ctype.h>
 14 #include <string>
 15 #include <iostream>
 16 #include <sstream>
 17 #include <vector>
 18 #include <queue>
 19 #include <stack>
 20 #include <map>
 21 #include <list>
 22 #include <set>
 23 #include <algorithm>
 24 #define INF 0x3f3f3f3f
 25 #define LL long long
 26 #define eps 1e-4
 27 #define maxn 210
 28 using namespace std;
 29 double X[2*maxn];
 30 double Y[2*maxn];
 31 struct TwoSAT
 32 {
 33     int n;
 34     vector<int> G[maxn*2];
 35     bool mark[maxn*2];
 36     int S[maxn*2],c;
 37     bool dfs(int x)
 38     {
 39         if (mark[x^1]) return false;//真假同时被标记，逻辑矛盾
 40         if (mark[x]) return true;//x被标记，意味着下面的节点也被标记，思想是记忆化搜索
 41         mark[x]=true;
 42         S[c++]=x;
 43         for(int i=0; i<G[x].size(); i++)
 44         if(!dfs(G[x][i])) return false; //同一个强联通分量应该表上同一种颜色
 45         return true;
 46     }
 47     void init(int n)
 48     {
 49         this->n=n;
 50         for(int i=0; i<n*2; i++) G[i].clear();
 51         memset(mark,0,sizeof(mark));
 52     }
 53     void add_clause(int x,int y)//x,y不能同时存在
 54     {
 55         G[x].push_back(y^1);
 56 //        cout<<x<<"->"<<(y^1)<<endl;
 57         G[y].push_back(x^1);
 58 //        cout<<y<<"->"<<(x^1)<<endl;
 59     }
 60     bool solve()
 61     {
 62         for(int i=0; i<n*2; i+=2)
 63         {
 64             if(!mark[i] && !mark[i^1])
 65             {
 66                 c=0;//记得清零
 67                 if(!dfs(i))//将i标记为true
 68                 {
 69                     while(c>0) mark[S[--c]]=false;
 70                     if (!dfs(i^1)) return false;
 71                 }
 72             }
 73         }
 74         return true;
 75     }
 76 } sat;
 77 double dis(double x1,double y1,double x2,double y2)
 78 {
 79     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 80 }
 81 bool F(int n,double rad)
 82 {
 83     sat.init(n);
 84     for(int i=1; i<2*n; i++)//枚举两两组之间
 85     for(int j=0; j<i; j++)
 86     {
 87         if (i==(j^1)) continue;//Kの，j^1要加括号，深坑
 88         if (2*rad-dis(X[j],Y[j],X[i],Y[i])>eps)
 89             sat.add_clause(i,j);
 90     }
 91     return (sat.solve());
 92 }
 93 int n;
 94 int main()
 95 {
 96     while(cin>>n)
 97     {
 98         for(int i=0; i<n; i++)
 99             cin>>X[2*i]>>Y[2*i]>>X[2*i+1]>>Y[2*i+1];//注意建模时对应的点
100         double R=9999999,L=0;
101         while(R-L>eps)
102         {
103             double M=(R+L)/2;
104             if (F(n,M)) L=M;
105             else R=M;
106         }
107         printf("%.2lf
",L);
108     }
109     return 0;
110 }