小 x伤心的走上了 Star way to heaven。
到天堂的道路是一个笛卡尔坐标系上一个 n*m的长方形通道 顶点在0,0 和 。
小 n,m 从最左边任意一点进入,从右边任意一点走到天堂,最左最右的距离n为 ,上下边界距离m为 。
其中长方形有 k个 ,每个k 都有一个整点坐标,star的大小可以忽略不计。
每个star 以及长方形上下两个边缘宇宙的边界都有引力,所以为了成功到达 小w 离他们越远越好。
请问小w走到终点的路径上,距离所有星星以及边界的最小距离最大值可以为多少?
输入格式
一行三个整数 。
接下来k行,每行两个整数 表示一个点的坐标。
输出格式
一行一个数表示答案。保留到小数点后9位。
样例
样例输入
10 5 2
1 1
2 3
样例输出
1.118033989
给出一个个星星,以某一个半径,封住一列,使其变为两部分,求这个半径最小为多少
我们可以二分ans,然后用dfs或bfs来进行判断,但是,实际上,用这个方法会超时
于是,我们可以换一个思路,其实,我们可以从最上面为起点,构造最小生成树,如果说,
一个点的半径能够触碰到最下面,那就说明,已经成功封闭了
那具体该如何操作呢?
这里不能用常用的kruskal,而是用比较冷门的prim,首先,每一个初始值为每一个点到最上面的距离,然后取出最小的也就是离上面最近的,然后,用这一个点,更新每一点的最低值,其中,算出最大值即可
哪有什么时候结束呢,我们可以在开一个,为最上面到最下面的最小值,如果说,这个值被选中了,就说明已经被封闭来,直接输出即可,但是求的是半径,所以要/2
疑问?m不该是列吗,为什么变成来上下边界距离m
#include<bits/stdc++.h>
using namespace std;
int n;
double m;
int k;
double x[10005];
double y[10005];
double dist[100005];
int vis[10005];
double js(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
scanf("%d %lf %d",&n,&m,&k);
for(int i=1;i<=k;i++)
{
scanf("%lf %lf",&x[i],&y[i]);
}
for(int i=1;i<=k;i++)
{
dist[i]=m-y[i];
}
dist[k+1]=m;
double ans=-1;
dist[0]=1000000;
for(int j=1;j<=k+1;j++)
{
int mq=0;
for(int i=1;i<=k+1;i++)
{
if(!vis[i]&&dist[i]<dist[mq]){
mq=i;
}
}
ans=max(dist[mq],ans);
if(mq==k+1)
{
printf("%.9lf",ans/2);
return 0;
}
for(int i=1;i<=k;i++)
{
dist[i]=min(dist[i],js(x[i],y[i],x[mq],y[mq]));
}
dist[k+1]=min(dist[k+1],y[mq]);
vis[mq]=1;
}
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章