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 = 0110     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 = 1117     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 = 0124     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 = 1135     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 = 0144     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 -> y153     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 Node162 {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\n", L);212 }213 void output()214 {215     //216 }217 int main()218 {219     // std::ios_base::sync_with_stdio(false);220 // #ifndef ONLINE_JUDGE221 //     freopen("in.cpp", "r", stdin);222 // #endif223 224     while (~scanf("%d", &n))225     {226         init();227         input();228         solve();229         output();230     }231     return 0;232 }