开始的时候二分的地方写错了，一直找不出错，搜搜别人的题解，一对比就知道了
每次输入的是一对点，只能在其中选一个点画圆，然后二分枚举半径，把不矛盾的点连一条边，建好图后，判断强连通是否有解即可，即会不会有某一对点属于同一个强连通分量中，如果都不会，则半径合法
View Code
1 #include<stdio.h>
2 #include<string.h>
3 #include<vector>
4 #include<math.h>
5 #include<algorithm>
6 using namespace std;
7 const int MAX = 500;
8 vector<int> edge[MAX];
9 int st[MAX];
10 int dfn[MAX],low[MAX];
11 int top,btype,tdfn;//btype:连通块的个数
12 int belong[MAX];//点属于哪个连通块
13 bool ins[MAX];
14 struct point {
15 double x,y;
16 }p1[200],p2[200];
17 int n;
18 double dis(point a,point b)
19 {
20 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
21 }
22 void dfs(int s)
23 {
24 int i,t;
25 dfn[s]=low[s]=++tdfn;
26 ins[s]=true;
27 st[++top]=s;
28 for(i=0;i<edge[s].size();i++)
29 {
30 t=edge[s][i];
31 if(!dfn[t])
32 {
33 dfs(t);
34 if(low[t]<low[s]) low[s]=low[t];
35 }
36 else if(ins[t] && dfn[t]<low[s]) low[s]=dfn[t];
37 }
38 if(dfn[s]==low[s])
39 {
40 btype++;
41 do
42 {
43 t=st[top--];
44 ins[t]=false;
45 belong[t]=btype;
46 }while(t!=s);
47 }
48 }
49 void SCC(int n)
50 {
51 int i;
52 top=btype=tdfn=0;
53 memset(ins,false,sizeof(ins));
54 memset(dfn,0,sizeof(dfn));
55 for(i=1;i<=n;i++)
56 if(!dfn[i])
57 dfs(i);
58 }
59 void build(double r)
60 {
61 int i,j;
62 for(i=1;i<=n;i++)
63 for(j=i+1;j<=n;j++)
64 {
65 if(dis(p1[i],p1[j])<r*2)
66 {
67 edge[i].push_back(j+n);
68 edge[j].push_back(i+n);
69 }
70 if(dis(p1[i],p2[j])<r*2)
71 {
72 edge[i].push_back(j);
73 edge[j+n].push_back(i+n);
74 }
75 if(dis(p2[i],p1[j])<r*2)
76 {
77 edge[i+n].push_back(j+n);
78 edge[j].push_back(i);
79 }
80 if(dis(p2[i],p2[j])<r*2)
81 {
82 edge[i+n].push_back(j);
83 edge[j+n].push_back(i);
84 }
85 }
86 }
87
88 bool judge(double mid)
89 {
90 int i;
91 for(i=0;i<=2*n;i++) edge[i].clear();
92 build(mid);
93 SCC(2*n);
94 for(i=1;i<=n;i++)
95 if(belong[i]==belong[i+n])
96 return false;
97 return true;
98 }
99 int main()
100 {
101 int i,j,k;
102 while(scanf("%d",&n)!=EOF)
103 {
104 for(i=1;i<=n;i++)
105 scanf("%lf%lf%lf%lf",&p1[i].x,&p1[i].y,&p2[i].x,&p2[i].y);
106 double left=0,right=20001;
107 double ans=0;
108 while(right-left>1e-6)
109 {
110 double mid=(left+right)/2.0;
111 if(judge(mid))
112 {
113 ans=mid;
114 left=mid;
115 }
116 else right=mid;
117 }
118 printf("%.2lf\n",ans);
119 }
120 return 0;
121 }