SDOI2012 Round1 day2 拯救小云公主(dis)解题报告
2024-10-21 12:46:59
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
typedef double real; #define setfire(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);
#define fre(name) freopen(#name".txt","r",stdin);
#define debug(x) cout<<#x<<" "<<x<<'\n';
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif const int N=;
const real inf=1e14;
struct M{int x,y;}a[N];
int n,row,line,S,T,q[N*];bool vis[N*];
real ans,g[N][N],dis[N];
double get_dis(M a,M b){
int tx=a.x-b.x,ty=a.y-b.y;
return sqrt(tx*tx+ty*ty);
}
void init(){
scanf("%d%d%d",&n,&row,&line);S=n+;T=S+;
for(int i=,x,y;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
}
void mapping(){
for(int i=;i<=n;i++)
// g[S][i]=g[i][S]=min(a[i].x-1,row-a[i].x),//居然还90
// g[T][i]=g[i][T]=min(a[i].y-1,line-a[i].y);
g[S][i]=g[i][S]=min(a[i].x-,line-a[i].y),
g[T][i]=g[i][T]=min(a[i].y-,row-a[i].x);
for(int i=;i<=n;i++)
for(int j=i;j<=n;j++)
g[i][j]=g[j][i]=get_dis(a[i],a[j])/2.0;
ans=inf;
for(int i=;i<=n;i++)
ans=min(ans,get_dis(a[i],(M){,})),
ans=min(ans,get_dis(a[i],(M){row,line}));
g[S][T]=g[T][S]=min(row-,line-);
}
void spfa(){
for(int i=;i<=T;i++) vis[i]=,dis[i]=inf;
unsigned short h=,t=;real dl;
q[t]=S;dis[S]=;
while(h!=t){
int x=q[++h];vis[x]=;//少打个标记90变30
for(int i=;i<=T;i++){
if(x!=i&&(dl=max(dis[x],g[x][i]))<dis[i]){
dis[i]=dl;
if(!vis[i]){
vis[i]=;
q[++t]=i;
}
}
}
}
}
int main(){
setfire(dis);
init();
mapping();
spfa();
ans=min(ans,dis[T]);
printf("%.2lf",ans);
return ;
}
最新文章
- Linux测试环境部署jdk(一)
- JVM &; Server &; Connector &; Context Relationship
- [字符编码]Invalid byte 1 of 1-byte UTF-8 sequence终极解决方案
- CSS实现水平垂直同时居中的5种思路
- DFS cdoevs 3100 蜗牛
- Gson简要使用
- C#多线程与异步的区别
- HTML5自学笔记[ 23 ]canvas绘图基础7
- MVC常用 ActionResult
- 在线App开发平台——应用之星傻瓜式开发平台
- C#入门经典(3-窗体应用程序-第二章要点)
- make[1]: *** [/workopenwrt/trunk/staging_dir/target-mipsel_24kec+dsp_uClibc-0.9.33.2/stamp/.tools_install_nnnnn] Error 2 make[1]: Leaving directory `/work/openwrt/trunk&#39; make: *** [world]
- CentOS 7安装部署ELK 6.2.4-SUCCESS
- Oracle创建表sql语句
- 手机浏览器 - 如何消除<;a>;标签在点击时的蓝色底色?
- MySQL8常见客户端和启动相关参数
- binTreepreorderTraversal二叉树前序遍历
- python-flask-wtforms
- set_magic_quotes_runtime set_magic_quotes_gpc
- Kafka中的zookeeper-shell.sh