思路：如题
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #define Maxm 100010 #define eps 1e-4 using namespace std; int vi[220],head[220],e,n,m,id[220],lab,num,dfn[220],low[220],Stack[220],top; double Max; struct Point{ double x,y; }p[210]; struct Edge{ int u,v,next; }edge[Maxm]; void init() { memset(vi,0,sizeof(vi)); memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); lab=num=top=0; e=0; } void add(int u,int v) { edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++; } double Dis(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void Tarjan(int u) { int i,j,v; dfn[u]=low[u]=++lab; Stack[top++]=u; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } if(vi[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { ++num; do{ i=Stack[--top]; vi[i]=0; id[i]=num; }while(i!=u); } } int solve() { int i,j; for(i=1;i<=2*n;i++) if(!dfn[i]) Tarjan(i); for(i=1;i<=n;i++) if(id[i]==id[i+n]) return 0; return 1; } void buildGraphic(double mid) { init(); int i,j; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(Dis(p[i],p[j])<mid) add(i,j+n),add(j,i+n); if(Dis(p[i+n],p[j+n])<mid) add(i+n,j),add(j+n,i); } for(j=1+n;j<=2*n;j++) { if(j==i+n) continue; if(Dis(p[i],p[j])<mid) add(i,j-n),add(j,i+n); } } } int main() { int i,j; while(scanf("%d",&n)!=EOF) { init(); for(i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y); double l,r,mid; l=0,r=40000; while(l+eps<r) { mid=(l+r)/2; buildGraphic(mid*2); if(solve()) l=mid; else r=mid; } printf("%.2lf ",l); } return 0; }