题解：
2-sat
和上一题差不多
只不过是一个圆
卡精度卡了好久。。。
代码：
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=405; double x[N],y[N],aans; int flag[N],n,ne[4*N*N],fi[N],zz[4*N*N],num; int t,zhan[N],T,dfn[N],m,l,q,ans,low[N],an[N]; void jb(int x,int y) { ne[++num]=fi[x]; fi[x]=num; zz[num]=y; } void dfs(int x) { low[x]=dfn[x]=++l; zhan[++t]=x; flag[x]=true; for (int i=fi[x];i!=0;i=ne[i]) { if (an[zz[i]])continue; if(!dfn[zz[i]])dfs(zz[i]); if(!flag[zz[i]])low[x]=min(low[x],dfn[zz[i]]);else low[x]=min(low[x],low[zz[i]]); } if (dfn[x]==low[x]) { ans++; while (zhan[t]!=x) { flag[zhan[t]]=false; an[zhan[t--]]=ans; } an[zhan[t--]]=ans; flag[x]=false; } } void init() { ans=num=l=0; memset(fi,0,sizeof fi); memset(an,0,sizeof an); memset(dfn,0,sizeof dfn); } void build(double r) { init(); for (int i=0;i<2*n;i++) for (int j=i+1;j<2*n;j++) if (i%n!=j%n) if (sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))<=r) { jb(i,(j+n)%(2*n)); jb(j,(i+n)%(2*n)); } } int main() { while (~scanf("%d",&n)) { for (int i=0;i<n;i++) scanf("%lf%lf%lf%lf",&x[i],&y[i],&x[i+n],&y[i+n]); double l=0,r=2e9;aans=0; for (int kk=0;kk<50;kk++) { double mid=(l+r)/2,k=0; build(mid); for (int i=0;i<2*n;i++) if (!dfn[i])dfs(i); for (int i=0;i<n;i++) if (an[i]==an[i+n]) {r=mid;k=1;break;} if (!k)l=aans=mid; } printf("%.2lf ",aans/2); } }