1 #include<cstdio>  2 #include<algorithm>  3 #include<cstring>  4 #include<cmath>  5 using namespace std;  6   7 struct E  8 {  9     int next, y; 10 } edge[40010]; 11 int col[210], dfn[210], low[210], stack[210], en[210], x[210], y[210]; 12 int esize, n, top, ti1, cnt; 13 double d[210][210]; 14 const double eps = 1e-8; 15 void insert(int u, int v) 16 { 17     edge[++esize].y = v; 18     edge[esize].next = en[u]; 19     en[u] = esize; 20 } 21 void dfs(int x) 22 { 23     //printf("%d %d\n", x, time); 24     dfn[x] = low[x] = ti1 ++; 25     stack[top++] = x; 26     for (int t = en[x]; t != -1; t = edge[t].next) 27     { 28         int y = edge[t].y; 29         if (dfn[y] == -1){ 30             dfs(y); 31             if (low[y] < low[x]) low[x] = low[y]; 32         } 33         else if (col[y] == -1 && low[y] < low[x]){  //low[y] can be replaced by dfn[y], equal? not equal but make no difference to scc 34             low[x] = low[y]; 35         } 36     } 37     if (dfn[x] == low[x]) 38     { 39         cnt ++; 40         while(stack[--top] != x) col[stack[top]] = cnt; 41         col[x] = cnt; 42     } 43 } 44 bool ok(double r) 45 { 46     //new map 47     memset(en, -1, sizeof(en)); 48     esize = 0; 49     for (int i = 0; i < n; i++) 50         for (int j = i + 1; j < n; j++) 51         { 52             if (d[i][j] < r * 2.0){ 53                 insert(i, j + n); 54                 insert(j, i + n); 55             } 56             if (d[i][j+n] < r * 2.0){ 57                 insert(i, j); 58                 insert(j + n, i + n); 59             } 60             if (d[i+n][j] < r * 2.0){ 61                 insert(i + n, j + n); 62                 insert(j, i); 63             } 64             if (d[i+n][j+n] < r * 2.0){ 65                 insert(j + n, i); 66                 insert(i + n, j); 67             } 68         } 69     //printf("r is %lf, esize is %d\n", r, esize); 70     //tarjan dfs 71     memset(col, -1, sizeof(col)); 72     memset(low, -1, sizeof(low)); 73     memset(dfn, -1, sizeof(dfn)); 74     top = 0; ti1 = 0; cnt = 0; 75     for (int i = 0; i < 2 * n; i++) 76         if (dfn[i] == -1) dfs(i); 77     //judge 78     //for (int i = 0; i < n; i++) 79     //    printf("color: %d %d %d\n", i, col[i], col[i+n]); 80     for (int i = 0; i < n; i++) 81         if (col[i] == col[i + n]) { 82         //    printf("%d", col[i]); 83             return false;} 84     return true; 85 } 86 double dis(int i, int j) 87 { 88     return sqrt(double(x[i] - x[j]) * double(x[i] - x[j]) + 89             double(y[i] - y[j]) * double(y[i] - y[j])); 90 } 91 int main() 92 { 93     while(scanf("%d", &n) != EOF) 94     { 95         double max = 0; 96         for (int i = 0; i < n; i++) 97         { 98             scanf("%d%d%d%d", &x[i], &y[i], &x[i+n], &y[i+n]); 99         }100         for (int i = 0; i < n; i++)101             for (int j = i + 1; j < n; j++)102             {103                 d[i][j] = d[j][i] = dis(i, j);104                 if (d[i][j] > max) max = d[i][j];105                 d[j][i+n] = d[i+n][j] = dis(i+n, j);106                 if (d[i+n][j] > max) max = d[i+n][j];107                 d[i][j+n] = d[j+n][i] = dis(i, j+n);108                 if (d[i][j+n] > max) max = d[i][j+n];109                 d[i+n][j+n] = d[j+n][i+n] = dis(i+n, j+n);110                 if (d[i+n][j+n] > max) max = d[i+n][j+n];111             }112     //    for (int i = 0; i < n; i++)113     //        for (int j = i + 1; j < n; j++)114     //        {115     //            printf("%lf %lf %lf %lf\n", d[i][j], d[i][j+n], d[i+n][j], d[i+n][j+n]);116     //        }117         double l = 0.0, r = max, ans = 0.0;118         while (l + eps <= r)119         {120     //        puts("yes");121             double mid = (l + r) / 2.0;122     //        printf("%lf\n", mid);123             if (ok(mid))124             {125     //            printf("%lf is ok\n", mid);126                 if (mid > ans)127                     ans = mid;128                 l = mid + eps;129             }130             else131                 r = mid - eps;132         }133         printf("%.2lf\n", ans);134     }135     return 0;136 }