飞机票： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5040

从这一题我对2-sat有更深的了解了。。。起先以为2-sat要添加一定可行的边。。。其实不然。。。要求添加可能可以的边。。。意思就是说两个组每个组2个人A1 A2,B1,B2 如果A1选了不能选B1，那么不管A2选了能不能选B1。。。都添加A2 B1这条边搞了一天2-sat 什么鬼~~~反正现在深入了解了。。。好了。。直接正题~~~

分析。。这题就是说给你n个组。每个组有两个球。。每个球有坐标。。从每个组里选择一个球。。且所有球不重叠。。。球最大球径是多少。。。其实就是2-sat问题。。。怎么搞呢？？先求出每队之间的距离。。。即一共有四个距离。。。即(A1,B1),(A1,B2),(A2,B1),(A2,B2) 三维距离很简单。。。((x1-x2）^2+(y1-y2)^2+(z1-z2)^2)^0.5即可。。搜噶然后二分球径。。。这里可以剪下枝。。。怎么搞呢。。。先从上面的距离选出最大的距离作为r,l为0。。。然后在循环里面可以判断下那四个距离是否都小于R，如果小于R。。则不符合条件。。直接继续二分。。。如果有一个可以则。。。根据2-sat建边。。。这里得知道要添加可能的边（起先不知道。。Wa到死）一共有四种可能。。所以有4种添边方案。。。然后每次二分跑一下tarjan。。。如果符合条件。。则l变为mid+e...这里e是定义的精度。。。如果不可以。。那r就要变为mid-e...当可行的时候。。。可以定义一个double记录最大符合条件的球径。。。其实起先我还卡了一下为什么距离要跟球径的两倍比较。。。后来想了一下球可以转的啊。。。太菜了。。。最后精度又是个问题。。。但是只要保留4位小数就可以了。。。因为是spj。。。然后啪啪啪！！！AC！！！

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=456;
const double e=0.0001;
struct he
{
    int a,b,c;
} JLJ[maxn];
vector<int> V[maxn];
double dist[maxn][maxn];
int n;
void init()
{
    for(int i=0; i<n; i++)
    {
        scanf("%d%d%d",&JLJ[i*2].a,&JLJ[i*2].b,&JLJ[i*2].c);
        scanf("%d%d%d",&JLJ[i*2+1].a,&JLJ[i*2+1].b,&JLJ[i*2+1].c);
    }

}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
double cal(double a,double b,double c,double d,double e,double f)
{
    return sqrt((a-d)*(a-d)+(b-e)*(b-e)+(c-f)*(c-f));
}
void play()
{
    double MAX=0;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            dist[i*2][j*2]=cal(JLJ[i*2].a,JLJ[i*2].b,JLJ[i*2].c,JLJ[j*2].a,JLJ[j*2].b,JLJ[j*2].c);
            dist[i*2][j*2+1]=cal(JLJ[i*2].a,JLJ[i*2].b,JLJ[i*2].c,JLJ[j*2+1].a,JLJ[j*2+1].b,JLJ[j*2+1].c);
            dist[i*2+1][j*2]=cal(JLJ[i*2+1].a,JLJ[i*2+1].b,JLJ[i*2+1].c,JLJ[j*2].a,JLJ[j*2].b,JLJ[j*2].c);
            dist[i*2+1][j*2+1]=cal(JLJ[i*2+1].a,JLJ[i*2+1].b,JLJ[i*2+1].c,JLJ[j*2+1].a,JLJ[j*2+1].b,JLJ[j*2+1].c);
            MAX=max(MAX,dist[i*2][j*2]);
            MAX=max(MAX,dist[i*2][j*2+1]);
            MAX=max(MAX,dist[i*2+1][j*2]);
            MAX=max(MAX,dist[i*2+1][j*2+1]);
        }
    }
    double l=0;
    double r=MAX;
    double over=0;
    while(l<=r)
    {
        double mid=(l+r)/2;
        double d=mid*2;
        bool flag=1;
        for(int i=0; i<=2*n; i++)V[i].clear();
        for(int i=0; i<n; i++)
        {  if(!flag)break;
            for(int j=i+1; j<n; j++)
            {
                if(dist[i*2][j*2]<d&&dist[i*2+1][j*2]<d&&dist[i*2][j*2+1]<d&&dist[i*2+1][j*2+1]<d)
                {
                    flag=0;
                    break;
                }
                if(dist[i*2][j*2+1]<d)
                {
                    V[i*2].push_back(j*2);
                    V[j*2+1].push_back(i*2+1);
                }
                if(dist[i*2][j*2]<d)
                {
                        V[i*2].push_back(j*2+1);
                        V[j*2].push_back(i*2+1);
                }
                if(dist[i*2+1][j*2+1]<d)
                {
                    V[i*2+1].push_back(j*2);
                    V[j*2+1].push_back(i*2);
                }
                if(dist[i*2+1][j*2]<d)
                {
                    V[i*2+1].push_back(j*2+1);
                    V[j*2].push_back(i*2);
                }

            }
        }
        if(!flag){
            r=mid-e;
            continue;
        }
        indexx=cntnum=0;
        scnt=-1;
        memset(dfn,-1,sizeof(dfn));
        memset(instack,0,sizeof(instack));
        for(int i=0; i<2*n; i++)
        {
            if(dfn[i]==-1)tarjan(i);
        }
        for(int i=0; i<n; i++)
        {
            if(belong[i*2]==belong[i*2+1])
            {
                flag=0;
                break;
            }
        }
        if(!flag)
        {
            r=mid-e;
            continue;
        }
        over=max(over,l);
        l=mid+e;

    }
    printf("%.4lf\n",over);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}