题意：给出一些点对，你可以在每对中任意选一个，只能选一个，放置一个炸弹，每个炸弹爆炸时都有一个效果范围，会波及到其放置点为圆心，半径为 r 的圆的范围，问如果要让任意两个圆都不相交（可以相切）的话，半径的最大值是多少。
二分+2-SAT
建图：只要一对点（i,j）的距离小于二分时候的mid的值，那么建立边（i,j'），（j',i）。
不过这题要注意精度。
#include<iostream> #include<queue> #include <cmath> using namespace std; const int N=209; const int inf=1<<30; const int M=50009; #define ep (1e-7) int n,tot,index,top,color; struct Node { int v,next; }e[M]; struct point { int x,y; }p[N]; int head[N],dfn[N],low[N],belong[N],sta[N],instack[N]; double dis[N]; double Dis(point a,point b) { return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void add(int a,int b) { e[tot].v=b; e[tot].next=head[a]; head[a]=tot++; } int min_(int a,int b) { if(a<b)return a; return b; } void tarjan(int u) { dfn[u]=low[u]=++index; sta[top++]=u; instack[u]=1; for(int i=head[u];i+1;i=e[i].next) { int v=e[i].v; if(!dfn[v]) { tarjan(v); low[u]=min_(low[u],low[v]); }else if(instack[v]) low[u]=min_(low[u],dfn[v]); } if(low[u]==dfn[u]) { int v; color++; do{ v=sta[--top]; instack[v]=0; belong[v]=color; }while(v!=u); } } void init() { memset(instack,0,sizeof(instack)); memset(dfn,0,sizeof(dfn)); memset(belong,0,sizeof(belong)); top=index=color=0; } int main() { int i,j; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) { scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y); } double right=2000.0,left=0; double mid; while(right-left>ep)//二分半径 { memset(head,-1,sizeof(head)); tot=0; mid=(right+left)/2.0; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(Dis(p[i],p[j])+ep<2*mid) { add(i,j+n); add(j,i+n); } if(Dis(p[i],p[j+n])+ep<2*mid) { add(i,j); add(j+n,i+n); } if(Dis(p[i+n],p[j])+ep<2*mid) { add(i+n,j+n); add(j,i); } if(Dis(p[i+n],p[j+n])+ep<2*mid) { add(i+n,j); add(j+n,i); } } } init(); for(i=1;i<=n*2;i++) { if(!dfn[i]) tarjan(i); } int flag=1; for(i=1;i<=n;i++) if(belong[i]==belong[i+n]) { flag=0; break; } if(flag) { left=mid; }else right=mid; } printf("%.2lf ",left); } return 0; }