传送门:Bomb Game

题意:给n对炸弹可以放置的位置(每个位置为一个二维平面上的点),每次放置炸弹是时只能选择这一对中的其中一个点,每个炸弹爆炸的范围半径都一样,控制爆炸的半径使得所有的爆炸范围都不相交(可以相切),求解这个最大半径.

分析:二分距离,由two-sat判可行性,建图时对于每两个炸弹的两个位置,互相判断一下是否冲突,冲突就建边。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 210
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,next;
edge() {}
edge(int v,int next):v(v),next(next) {}
} e[N*N];
int n,m,scc,step,top,tot;
int head[N],dfn[N],low[N],belong[N],Stack[N];
bool instack[N];
void init()
{
tot=;step=;
scc=;top=;
FILL(head,-);
FILL(dfn,);
FILL(low,);
FILL(instack,false);
}
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void tarjan(int u)
{
int v;
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head[u]; ~i; i=e[i].next)
{
v=e[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
scc++;
do
{
v=Stack[--top];
instack[v]=false;
belong[v]=scc;
}
while(v!=u);
}
}
int judge()
{
for(int i=; i<*n; i++)
if(!dfn[i])tarjan(i);
for(int i=; i<n; i++)
{
if(belong[i<<]==belong[i<<^])
{
return ;
}
}
return ;
} int lx[],ly[],rx[],ry[];
double dist(int a,int b,int x,int y)
{
return sqrt((double)(a-x)*(a-x)+(double)(b-y)*(b-y));
}
void build(double m)
{
for(int i=;i<n;i++)
for(int j=i+;j<n;j++)
{
if(dist(lx[i],ly[i],lx[j],ly[j])+eps<*m)addedge(i<<,j<<|),addedge(j<<,i<<|);
if(dist(lx[i],ly[i],rx[j],ry[j])+eps<*m)addedge(i<<,j<<),addedge(j<<|,i<<|);
if(dist(rx[i],ry[i],lx[j],ly[j])+eps<*m)addedge(i<<|,j<<|),addedge(j<<,i<<);
if(dist(rx[i],ry[i],rx[j],ry[j])+eps<*m)addedge(i<<|,j<<),addedge(j<<|,i<<);
}
}
void solve()
{
double l=,r=,ans=;
while(r-l>eps)
{
double m=(l+r)/;
init();
build(m);
if(judge())
{
ans=m;l=m;
}
else r=m;
}
printf("%.2f\n",ans);
}
int main()
{
int a,b,c,u,v;
char op[];
while(scanf("%d",&n)>)
{
for(int i=;i<n;i++)
{
scanf("%d%d%d%d",&lx[i],&ly[i],&rx[i],&ry[i]);
}
solve();
}
}

最新文章

  1. java学习笔记之IO一()
  2. Nodejs - 如何用 eventproxy 模块控制并发
  3. 读懂Android项目结构目录
  4. 改变seekbar的游标图片大小
  5. Linux系统调用列表
  6. PHP 中的随机数——你觉得可靠么?
  7. vmware9.0 安装ios10.8应该注意的地方
  8. YT工作日志-0911
  9. Python一个命令开启http下载服务器(可以局域网内共享文件)
  10. Android 注解框架对比
  11. UOJ#349. 【WC2018】即时战略
  12. nigix反向代理
  13. echarts使用笔记四:双Y轴
  14. Android性能优化案例研究
  15. python之json数据存储
  16. 微信小程序——星星评分
  17. FileUpload控件实现单按钮图片自动上传并带预览显示
  18. mdf, ldf文件导入到sql server 2005的方法
  19. SecureCRT上传下载文件
  20. CSU - 1334 -好老师(STL-map用法)

热门文章

  1. hdu 3998 (dp+最大流)
  2. ul不加宽高
  3. 用WebCollector制作一个爬取《知乎》并进行问题精准抽取的爬虫(JAVA)
  4. C++学习笔记3
  5. gbs build使用说明
  6. LLBL Gen Pro 5.0
  7. Salt Stack 官方文档翻译 - 一个想做dba的sa - 博客频道 - CSDN.NET
  8. Swift - 使用xib添加新界面
  9. Android API中被忽略的几个函数接口
  10. HDU 1863 畅通project (最小生成树是否存在)