2-SAT验证 + 二分半径
#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int maxn=8000+5; int M,N; double X1[maxn],Y1[maxn],X2[maxn],Y2[maxn]; int tot; double l,r,mid; struct TwoSAT { int n; vector<int> G[maxn*2]; bool mark[maxn*2]; int S[maxn*2],c; bool dfs(int x) { if(mark[x^1]) return false; if(mark[x]) return true; mark[x]=true; S[c++]=x; for(int i=0;i<G[x].size();i++) if(!dfs(G[x][i])) return false; return true; } void init(int n) { this->n=n; for(int i=0;i<n*2;i++) G[i].clear(); memset(mark,0,sizeof mark); } void add_clause(int x,int y) { G[x].push_back(y^1); G[y].push_back(x^1); } bool solve() { for(int i=0;i<2*n;i+=2) if(!mark[i]&&!mark[i+1]) { c=0; if(!dfs(i)) { while(c>0) mark[S[--c]]=false; if(!dfs(i+1)) return false; } } return true; } }; bool cmp(double xa,double ya,double xb,double yb) { double dis=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb)); if(dis>=2*mid) return 1; //不相交 else return 0;//相交 } int main() { while(~scanf("%d",&N)) { for(int i=0;i<N;i++) scanf("%lf%lf%lf%lf",&X1[i],&Y1[i],&X2[i],&Y2[i]); tot=30; l=0,r=20000; while(tot--) { mid=(l+r)/2; TwoSAT T; T.init(N); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(i==j) continue; if(cmp(X1[i],Y1[i],X1[j],Y1[j])==0) T.add_clause(2*i,2*j); if(cmp(X1[i],Y1[i],X2[j],Y2[j])==0) T.add_clause(2*i,2*j+1); if(cmp(X2[i],Y2[i],X1[j],Y1[j])==0) T.add_clause(2*i+1,2*j); if(cmp(X2[i],Y2[i],X2[j],Y2[j])==0) T.add_clause(2*i+1,2*j+1); } } if(T.solve()==0) r=mid; else l=mid; } printf("%.2lf ",mid); } return 0; }