题意:
给n对炸弹可以放置的位置(每个位置为一个二维平面上的点),每次放置炸弹是时只能选择这一对中的其中一个点,每个炸弹爆炸的范围半径都一样,控制爆炸的半径使得所有的爆炸范围都不相交(可以相切),求解这个最大半径.
思路：二分半径，建图再2-sat判有无解。
收获：原来tarjan执行后，在同一个强连通分量里的low［］也不一定相同，我以为一定相同，，直接用low来是否在一个判强连通里面。
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N = 222;int head[N];int n;struct Edge{int v,next;}es[N*N];struct P{double x,y;}poi[N];const double esp = 1e-6;int tmp[N],dfn[N],low[N],belong[N],scc,sta[N];int cnt,index,top;double dis(int u,int v){return sqrt((poi[u].x-poi[v].x)*(poi[u].x-poi[v].x)+(poi[u].y-poi[v].y)*(poi[u].y-poi[v].y));}void tarjan(int u){tmp[u]=1;dfn[u]=low[u]=++index;sta[++top]=u;for(int i=head[u];~i;i=es[i].next){int v=es[i].v;if(tmp[v]==0) tarjan(v);if(tmp[v]==1) low[u]=min(low[u],low[v]);}if(low[u]==dfn[u]){scc++;do{int v=sta[top];tmp[v]=2;belong[v]=scc;}while(sta[top–]!=u);}}void init(){memset(head,-1,sizeof(head));top=index=cnt=scc=0;memset(tmp,0,sizeof(tmp));}void inline add_edge(int u,int v){es[cnt].v=v;es[cnt].next=head[u];head[u]=cnt++;}void build(int u,int v,double r){if(dis(u,v)<2*r) add_edge(u,v^1),add_edge(v,u^1);}bool ok(double r){init();for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){int u=i*2,v=j*2;build(u,v,r);build(u,v^1,r);build(u^1,v,r);build(u^1,v^1,r);}for(int i=0;i<2*n;i++)if(tmp[i]==0) tarjan(i);for(int i=0;i<2*n;i++)if(belong[i]==belong[i^1]) return false;return true;}int main(){while(~scanf("%d",&n)){for(int i=0;i<n;i++){int a=2*i;scanf("%lf%lf%lf%lf",&poi[a].x,&poi[a].y,&poi[a^1].x,&poi[a^1].y);}double lb=0,ub=4e4;while(ub-lb>esp){double mid=(ub+lb)/2.0;if(ok(mid)) lb=mid;else ub=mid;}printf("%.2f\n",lb);}return 0;}
请让我们从容面对这离别之后的离别。
