裸的2-SAT，详见刘汝佳训练指南P-323
不过此题有个特别需要注意的地方：You should promise that there is still no overlap for any two balloons after rounded.
模版题，
代码如下：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map> #define LL long long
#define eps 1e-5
#define M 205
#define mod 1000000007 using namespace std; struct Point
{
int x, y, z;
Point() { }
Point(int x, int y, int z) : x(x), y(y), z(z) { }
void readPoint()
{
scanf("%d %d %d", &x, &y, &z);
}
};
struct TwoSAT
{
int n;
vector<int>G[M*2];
bool mark[M*2];
int S[M*2], c; bool dfs(int x)
{
if(mark[x^1]) return false;
if(mark[x]) return true;
mark[x] = true;
S[c++] = x;
for(int i = 0; i < (int)G[x].size(); ++i)
if(!dfs(G[x][i])) return false;
return true;
} void init(int n)
{
this->n = n;
for(int i = 0; i < n*2; ++i) G[i].clear();
memset(mark, 0, sizeof(mark));
} void add_clause(int x, int y)
{
G[x^1].push_back(y);
G[y^1].push_back(x);
} bool solve()
{
for(int i = 0; i < n*2; i+=2)
if(!mark[i] && !mark[i+1])
{
c = 0;
if(!dfs(i))
{
while(c>0) mark[S[--c]] = false;
if(!dfs(i+1)) return false;
}
}
return true;
}
};
Point poi[2*M];
int dcmp(double a)
{
if(fabs(a)<eps) return 0;
return a<0?-1:1;
}
double dis(Point a, Point b)
{
return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y)+1.0*(a.z-b.z)*(a.z-b.z));
}
int ok(int n, double R)
{
TwoSAT temp;
temp.init(n);
for(int i = 0; i < 2*n; ++i)
for(int j = i+1; j < 2*n; ++j)
if(dcmp(dis(poi[i], poi[j])-2*R)<0)
{
temp.add_clause(i^1, j^1);
}
return temp.solve();
}
int main ()
{
int n;
while(~scanf("%d", &n))
{
for(int i = 0; i < 2*n; ++i)
poi[i].readPoint();
double l = 0.0, r = dis(Point(0,0,0), Point(10000,10000,10000)), mid;
while(r-l>eps)
{
mid = (r+l)/2;
if(ok(n, mid))
l = mid;
else
r = mid;
}
double ans = (int)(mid*1000+0.5)/1000.0;//注意！！！
if(!ok(n, ans)) ans-=0.001;
printf("%.3lf\n", ans);
}
return 0;
}