二分距离2sat
2 1 1 1 -1 -1 -1 -1 1 2 1 1 -1 -1 1 -1 -1 1
1.41 1.00
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn=222; struct Edge { int to,next; }edge[maxn*maxn*3]; int Adj[maxn],Size; void init() { Size=0; memset(Adj,-1,sizeof(Adj)); } void Add_Edge(int u,int v) { edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++; } int Low[maxn],DFN[maxn],Belong[maxn],Instack[maxn],Stack[maxn]; int top,scc,Index; void tarjan(int u) { Low[u]=DFN[u]=++Index; Instack[u]=true; Stack[top++]=u; int v; for(int i=Adj[u];~i;i=edge[i].next) { v=edge[i].to; 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]) { scc++; do { v=Stack[--top]; Belong[v]=scc; Instack[v]=false; }while(v!=u); } } bool scc_solve(int n) { memset(DFN,0,sizeof(DFN)); memset(Instack,0,sizeof(Instack)); top=scc=Index=0; for(int i=0;i<2*n;i++) if(!DFN[i]) tarjan(i); for(int i=0;i<n;i++) { if(Belong[i<<1]==Belong[i<<1|1]) return false; } return true; } int n; int px[maxn][2],py[maxn][2]; int dist(int x,int y) { return x*x+y*y; } bool ck(int mid) { init(); for(int i=0;i<n;i++) { for(int a=0;a<2;a++) { for(int j=i+1;j<n;j++) { for(int b=0;b<2;b++) { if(dist(px[i][a]-px[j][b],py[i][a]-py[j][b])<mid) { Add_Edge(i*2+a,j*2+1-b); Add_Edge(j*2+b,i*2+1-a); } } } } } return scc_solve(n); } void solve() { int low=0,mid,high=2000000000,ans=-1; while(low+1<high) { mid=(low+high)/2.; if(ck(mid)) ans=mid,low=mid; else high=mid; } printf("%.2lf\n",sqrt((double)ans)/2.); } int main() { while(scanf("%d",&n)!=EOF) { double x1,x2,y1,y2; for(int i=0;i<n;i++) { scanf("%d%d%d%d",&px[i][0],&py[i][0],&px[i][1],&py[i][1]); } solve(); } return 0; }
HDOJ 3622 Bomb Game,布布扣,bubuko.com
原文:http://blog.csdn.net/ck_boss/article/details/24985505