好久没有2-sat了，此题当复习之用，二分求最大值+2-sat判断可行，此题主要跪于题意：The results should be rounded to three decimal
places. You should promise that there is still no overlap for any two balloons after rounded.
rounded是四舍五入的意思，按要求，3位之后要全部舍去，知道：printf（）,自动四舍五入。所有-0.0005
之后四舍五入即为要求。
#include<iostream>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
using namespace std;
int n;
struct points
{
int x,y,z;
};
points point[402];
inline int getdis(points a,points b) //三维
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
int vis[402];int dfn[402];int low[402];int scc[402];int numscc=0;
int times=0; stack<int>sta;int ins[402];
vector<vector<int> >v(402);
void clear()
{
for(int i=0;i<2*n;i++)
{
ins[i]=vis[i]=dfn[i]=low[i]=scc[i]=0;
v[i].clear();
}
numscc=times=0;
}
void tarjian(int u)
{
dfn[u]=low[u]=++times;
sta.push(u);
ins[u]=1;
int len=v[u].size();
for(int i=0;i<len;i++)
{
int uu=v[u][i];
if(!vis[uu])
{
vis[uu]=1;
tarjian(uu);
if(low[uu]<low[u])low[u]=low[uu];
}
else if(ins[uu]&&dfn[uu]<low[u])
low[u]=dfn[uu];
}
if(low[u]==dfn[u])
{
int cur;
numscc++;
do
{
cur=sta.top();
sta.pop();
ins[cur]=0;
scc[cur]=numscc;
}while(cur!=u);
}
}
bool check(double r)
{
clear();
for(int i=0;i<2*n-2;i++)
for(int j=(i%2==0?i+2:i+1);j<2*n;j++)
{
double dis=0.00+getdis(point[i],point[j]);
if(dis<4*r*r)
{
v[i].push_back(j^1);
v[j].push_back(i^1);
}
}
for(int i=0;i<2*n;i++)
{
if(!vis[i])
{
vis[i]=1;
tarjian(i);
}
}
for(int i=0;i<2*n;i+=2)
{
if(scc[i]==scc[i+1])
return 0;
}
return 1;
}
int main()
{
while(~scanf("%d",&n))
{ for(int i=0;i<2*n;i++)
scanf("%d%d%d",&point[i].x,&point[i].y,&point[i].z);
double l=0,r=100000,mid;
while(r-l>0.000001) //二分。
{
mid=(r+l)/2;
if(check(mid))
l=mid;
else
r=mid;
}
double ll=l-0.0005;
printf("%.3lf\n",ll);
}
return 0;
}