首页 > 代码库 > HDU 3622 Bomb Game
HDU 3622 Bomb Game
Description
\(n\) 个炸弹,每个炸弹有两个放置点,可以任选一个,问你最大的半径是多少.
Sol
二分+2-SAT+Tarjan.
首先二分一下答案.然后就成了一个2-SAT问题.
建模就是, \(i\) 如果和 \(j\) 的距离超过 \(x*2\),那么 \(i\) 只能选择 \(j\) ^ \(1\) 连边,同时 \(j\) 只能选择 \(i\) ^ \(1\) 连边.
最后用Tarjan所以下环,如果两个点在一个环中,那么就不合法.
Code
#include <bits/stdc++.h>using namespace std;#define F first#define S second#define mpr make_pair#define sqr(x) ((x)*(x))const int N = 205;const double eps = 1e-5;typedef pair< int,int > pr;typedef pair< pr,pr > prr;int n,c,cnt,cntb;pr a[N];vector< int > g[N];int d[N],b[N];int stk[N],instk[N],top;inline int in(int x=0) { scanf("%d",&x);return x; }void clr() { cntb=cnt=top=0; for(int i=0;i<N;i++) g[i].clear(); memset(d,0,sizeof(d)),memset(b,0,sizeof(b)),memset(instk,0,sizeof(instk));}double Dist(pr x,pr y) { return sqrt((double)sqr(x.F-y.F)+sqr(x.S-y.S)); }void Tarjan(int u,int fa) { d[u]=++cnt,stk[++top]=u,instk[u]=1;int dfsn=cnt; for(int i=0,v;i<(int)g[u].size();i++) if((v=g[u][i])!=fa) { if(!d[v]) Tarjan(v,u); if(instk[v]) d[u]=min(d[u],d[v]); } if(d[u]==dfsn) { for(++cntb;stk[top]!=u;top--) { b[stk[top]]=cntb,instk[stk[top]]=0; }b[stk[top]]=cntb,instk[stk[top--]]=0; }// cout<<u<<":"<<d[u]<<" "<<dfsn<<endl;}int check(double x) { clr(); for(int i=0;i<c;i++) for(int j=i&1 ? i+1 : i+2;j<c;j++) if(Dist(a[i],a[j])<x*2) g[i].push_back(j^1),g[j].push_back(i^1);// cout<<"("<<i<<","<<j<<")"<<Dist(a[i],a[j])<<endl, for(int i=0;i<c;i++) if(!d[i]) Tarjan(i,i); /* cout<<x<<endl; for(int i=0;i<c;i++) { cout<<i<<":"<<endl; for(int j=0;j<(int)g[i].size();j++) cout<<g[i][j]<<" "; cout<<endl; } for(int i=0;i<c;i++) cout<<b[i]<<" ";cout<<endl; cout<<"-------------------------"<<endl;*/ for(int i=0;i<c;i++) if(b[i]==b[i^1]) return 0; return 1;}int main() {// freopen("in.in","r",stdin); while(~scanf("%d",&n)) { c=0; for(int i=1;i<=n;i++) { int x=in(),y=in(); a[c++]=mpr(x,y); x=in(),y=in(); a[c++]=mpr(x,y); } double l=0.0,r=20000.0,mid; while(r-l > eps) { mid=(l+r)/2.0; if(check(mid)) l=mid; else r=mid; }printf("%.2lf\n",mid); }return 0;}
HDU 3622 Bomb Game
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。