ZOJ 3717 Balloon (二分+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 = 410;
 23 const int maxm = 410 * 410;
 24 const int inf = 0x3f3f3f3f;
 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL;
 26 const double INF = 1e30;
 27 const double eps = 1e-8;
 28 const int P[4] = {0, 0, -1, 1};
 29 const int Q[4] = {1, -1, 0, 0};
 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1};
 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1};
 32 /**
 33 *2-SAT模板: 按字典序排列结果
 34 *输入：按照法则添加边(参数为2*i或者2*i+1)
 35 *运行：先init(n),再add(),再solve()
 36 *注意：add(2*i,2*j)才行
 37 *输出：vis[](1表示选中),solve()(是否有解)
 38 */
 39 // const int maxn = 0;
 40 // const int maxm = 0;
 41 struct Edge
 42 {
 43     int u, v;
 44     int next;
 45 };
 46 struct TwoSAT
 47 {
 48     int n, en;
 49     Edge edge[maxm];
 50     int head[maxn];
 51     int vis[maxn], S[maxn];
 52     int cnt;
 53 
 54     void init(int _n = 0)
 55     {
 56         n = _n;
 57         memset(head, -1, sizeof(head));
 58         en = 0;
 59         memset(vis, 0, sizeof(vis));
 60     }
 61 
 62     void addse(int u, int v)
 63     {
 64         edge[en].u = u;
 65         edge[en].v = v;
 66         edge[en].next = head[u];
 67         head[u] = en++;
 68     }
 69 
 70     bool dfs(int u)
 71     {
 72         if (vis[u ^ 1])return 0;
 73         if (vis[u])return 1;
 74         vis[u] = 1;
 75         S[cnt++] = u;
 76         for (int i = head[u]; i != -1; i = edge[i].next)
 77         {
 78             if (!dfs(edge[i].v))return 0;
 79         }
 80         return 1;
 81     }
 82 
 83     bool solve()
 84     {
 85         for (int i = 0; i < 2 * n; i += 2)
 86         {
 87             if (vis[i] || vis[i ^ 1])continue;
 88             cnt = 0;
 89             if (!dfs(i))
 90             {
 91                 while (cnt)vis[S[--cnt]] = 0;
 92                 if (!dfs(i ^ 1))return 0;
 93             }
 94         }
 95         return 1;
 96     }
 97 
 98     /// x AND y = 1
 99     void add_and_one(int x, int y)
100     {
101         addse(x ^ 1, y);
102         addse(y ^ 1, x);
103         addse(x, y);
104         addse(y ^ 1, x ^ 1);
105         addse(y, x);
106         addse(x ^ 1, y ^ 1);
107     }
108 
109     /// x AND y = 0
110     void add_and_zero(int x, int y)
111     {
112         addse(x, y ^ 1);
113         addse(y, x ^ 1);
114     }
115 
116     /// x OR y = 1
117     void add_or_one(int x, int y)
118     {
119         addse(x ^ 1, y);
120         addse(y ^ 1, x);
121     }
122 
123     /// x OR y = 0
124     void add_or_zero(int x, int y)
125     {
126         addse(x, y ^ 1);
127         addse(y, x ^ 1);
128         addse(x, y);
129         addse(y ^ 1, x ^ 1);
130         addse(x ^ 1, y ^ 1);
131         addse(y, x);
132     }
133 
134     /// x XOR y = 1
135     void add_xor_one(int x, int y)
136     {
137         addse(x ^ 1, y);
138         addse(y ^ 1, x);
139         addse(x, y ^ 1);
140         addse(y, x ^ 1);
141     }
142 
143     /// x XOR y = 0
144     void add_xor_zero(int x, int y)
145     {
146         addse(x ^ 1, y ^ 1);
147         addse(y, x);
148         addse(x, y);
149         addse(y ^ 1, x ^ 1);
150     }
151 
152     /// x -> y
153     void add_to(int x, int y)
154     {
155         addse(x, y);
156         addse(y ^ 1, x ^ 1);
157     }
158 } sat;
159 
160 int n;
161 struct Node
162 {
163     int x, y, z;
164     Node(int _x = -1, int _y = -1, int _z = -1): x(_x), y(_y), z(_z) {}
165 } node[maxn];
166 void init()
167 {
168     //
169 }
170 void input()
171 {
172     for (int i = 0; i < 2 * n; i++)
173     {
174         scanf("%d%d%d", &node[i].x, &node[i].y, &node[i].z);
175     }
176 }
177 void debug()
178 {
179     //
180 }
181 double dis(int a, int b)
182 {
183     return sqrt((node[a].x - node[b].x) * (node[a].x - node[b].x) + (node[a].y - node[b].y) * (node[a].y - node[b].y) + (node[a].z - node[b].z) * (node[a].z - node[b].z));
184 }
185 bool test(double r)
186 {
187     sat.init(n);
188     // for (int i = 0; i < n; i++)
189     // {
190     //     sat.add_xor_one(2 * i, 2 * i + 1);
191     // }
192     for (int i = 0; i < 2 * n; i++)
193     {
194         for (int j = i + 1; j < 2 * n; j++)
195         {
196             if (2 * r > dis(i, j))
197                 sat.add_and_zero(i, j);
198         }
199     }
200     return sat.solve();
201 }
202 void solve()
203 {
204     double L = 0, R = 20000;
205     while (L + eps < R)
206     {
207         double M = (L + R) / 2;
208         if (test(M)) L = M;
209         else R = M;
210     }
211     printf("%f
", L);
212 }
213 void output()
214 {
215     //
216 }
217 int main()
218 {
219     // std::ios_base::sync_with_stdio(false);
220 // #ifndef ONLINE_JUDGE
221 //     freopen("in.cpp", "r", stdin);
222 // #endif
223 
224     while (~scanf("%d", &n))
225     {
226         init();
227         input();
228         solve();
229         output();
230     }
231     return 0;
232 }