hdu 3622 Bomb Game (二分+2-sat)

Bomb GameTime Limit: 10000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3133    Accepted Submission(s): 1071

Problem DescriptionInputOutputSample InputSample OutputSource#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 205#define MAXN 40005#define mod 1000000007#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6typedef long long ll;using namespace std;int n,m,num,flag;double ans;double dist[maxn][maxn];int x[maxn],y[maxn];int head[maxn];int scc[maxn];int vis[maxn];int stack1[maxn];int stack2[maxn];struct edge{ int v,next;} g[MAXN];void init(){ memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); memset(scc,0,sizeof(scc)); stack1[0] = stack2[0] = num = 0; flag = 1;}void addedge(int u,int v){ num++; g[num].v = v; g[num].next = head[u]; head[u] = num;}void dfs(int cur,int &sig,int &cnt){ if(!flag) return; vis[cur] = ++sig; stack1[++stack1[0]] = cur; stack2[++stack2[0]] = cur; for(int i = head[cur]; i; i = g[i].next) { if(!vis[g[i].v]) dfs(g[i].v,sig,cnt); else { if(!scc[g[i].v]) { while(vis[stack2[stack2[0]]] > vis[g[i].v]) stack2[0] --; } } } if(stack2[stack2[0]] == cur) { stack2[0] --; ++cnt; do { scc[stack1[stack1[0]]] = cnt; int tmp = stack1[stack1[0]]; if((tmp >n && scc[tmp - n] == cnt) || (tmp <= n && scc[tmp + n] == cnt)) // 注意这里的‘=’号 { flag = false; return; } } while(stack1[stack1[0] --] != cur); }}void Twosat(){ int i,sig,cnt; sig = cnt = 0; for(i=0; i<n+n&&flag; i++) { if(!vis[i]) dfs(i,sig,cnt); }}double caldist(int k1,int k2){ double xx,yy; xx=x[k1]-x[k2]; yy=y[k1]-y[k2]; return sqrt(xx*xx+yy*yy);}void presolve(){ int i,j; for(i=1;i<=2*n;i++) { for(j=i+1;j<=2*n;j++) { dist[i][j]=dist[j][i]=caldist(i,j); } }}void build(double dd){ int i,j,t1,t2; for(i=1;i<=2*n;i++) { for(j=i+1;j<=2*n;j++) { if(dist[i][j]<2*dd) { t1=j>n?j-n:j+n; t2=i>n?i-n:i+n; addedge(i,t1); addedge(j,t2); } } }}void solve(){ int i,j; double le=0,ri=INF,mid; while(ri-le>eps) { mid=(le+ri)/2; init(); build(mid); Twosat(); if(flag) le=mid; else ri=mid; } ans=le;}int main(){ int i,j,t; while(~scanf("%d",&n)) { for(i=1;i<=n;i++) { scanf("%d%d%d%d",&x[i],&y[i],&x[i+n],&y[i+n]); } presolve(); solve(); printf("%.2f\n",ans); } return 0;}