/*
二分+2-sat
题意:在一个二维平面上给你n个炸弹,和2*n个位置,每一行的两个位置只能有一个放炸弹
现在炸弹爆炸有一个半径,当炸弹爆炸时两个炸弹的半径化成的圆不能相交,求最大半径
二分半径,
每次如果一个炸弹可放的两个位置中的一个与其他位置有矛盾,就进行建边,最后判断是否存在这样一组解
即可。
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define eps 1e-5
#define N 210
struct node {
int u,v,next;
}bian[N*N];
int head[N],dfn[N],low[N],stac[N],yong,index,top,vis[N],ans,belong[N];
void init() {
memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
memset(stac,0,sizeof(stac));yong=0;index=0;top=0;;memset(vis,0,sizeof(vis));ans=0;
memset(belong,0,sizeof(belong));
}
void addedge(int u,int v) {
bian[yong].u=u;
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
int Min(int v,int vv) {
return v>vv?vv:v;
}
void tarjan(int u) {
dfn[u]=low[u]=++index;
stac[++top]=u;
vis[u]=1;
int i;
for(i=head[u];i!=-1;i=bian[i].next) {
int v=bian[i].v;
if(!dfn[v]) {
tarjan(v);
low[u]=Min(low[u],low[v]);
}
else
if(vis[v])
low[u]=Min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
ans++;
int t;
do {
t=stac[top--];
belong[t]=ans;
vis[t]=0;
}while(t!=u);
}
}
struct nodee{
int u,v,index;
}f[N*N];
int n;
double distance(nodee d,nodee dd) {
return 1.0*(d.u-dd.u)*(d.u-dd.u)+1.0*(d.v-dd.v)*(d.v-dd.v);
}
int judge(double r) {
int i,j;
init();
for(i=0;i<2*n-1;i++)
for(j=i+1;j<2*n;j++) {
if(i==(j^1))continue;
if(distance(f[i],f[j])<(r*2)*(r*2)) {//如果有冲突就进行
addedge(i,j^1);
addedge(j,i^1);
}
}
for(i=0;i<2*n;i++)
if(!dfn[i])
tarjan(i);
for(i=0;i<n;i++)
if(belong[i*2]==belong[i*2+1])break;
if(i==n)return 1;
return 0;
}
int main() {
int i;
double left,right,mid;
while(scanf("%d",&n)!=EOF) {
for(i=0;i<n;i++)
scanf("%d%d%d%d",&f[i*2].u,&f[i*2].v,&f[i*2+1].u,&f[i*2+1].v);
right=2*10000.0*2;left=0.0;
while(right-left>eps) {
mid=(left+right)/2;
// printf("%.2f\n",mid);
if(judge(mid))left=mid+eps;
else
right=mid-eps;
}
printf("%.2f\n",left);
}
return 0;}
05-11 16:28
查看更多