Star Way To Heaven
阅读原文时间:2023年07月08日阅读:3

题目描述

小 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;
    }
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章