P7249题解

· · 题解

P7249 移动网络

在后面的叙述中，圆的横坐标就是它的圆心的横坐标，左右端点就是和 x 轴左边或右边的交点。

解题思路

点开题目，看到了“线段上的点离最近的点最远”。

典型二分，二分的就是这个求的答案（距离），因为它有单调性。

然后考虑 check 函数怎么写。如果线段上有一个点和所有给定点的距离都大于等于 mid，那么答案一定大于等于 mid。

换句话说，以每个给定点为圆心，mid 为半径作圆，把线段的一部分覆盖掉，如果线段还有未被覆盖的部分，那么答案要往大了取。

一堆线段能否覆盖一条大线段，看起来要排序……真的要吗？

给出点的坐标以横坐标为第一关键字，纵坐标为第二关键字升序排序。

好家伙，还有个条件没用！

如图，横坐标相同时，纵坐标大的完全没用。

所以只考虑相同横坐标时纵坐标绝对值小的点。

如果全程没有空白，相安无事。

而如果有空白，横坐标大的点的圆如果能帮前面的圆填补空白，那么它的右端点一定不会比前面所有圆的右端点的最大值更小。

下面给出解释。

设这个填补了空白的圆为圆 M，圆 N 是创造空白的那个圆及其后面的圆中的一个。

因为圆 N 不能填补空白，所以它太逊了。 所以它们的左端点没有圆 M 的左端点小。又因为圆 M 的横坐标更大，所以它的右端点一定更大。

所以用圆 M 的右端点更新最大连续覆盖的右端点一定不会更劣。

如图，假设红色的是被填补的空白，则圆 B 的右端点比圆 A 的大。

如果有空白但不能（完全）覆盖，就不更新最大覆盖右端点，直到出现了可以完全填补空白的圆，再根据上面的解释，把最大覆盖右端点更新。

去掉了使复杂度变得垃圾的排序以后，时间复杂度降为 O(n\times \log(\frac{10^9}{eps}))。

如果还有不明白，最好是私聊，或者评论区。

代码部分

#include <bits/stdc++.h>
using namespace std;
const double eps=0.0003;
int n,l;
int x[1000010],y[1000010];
bool check(double mid){//1表示线段上至少有地方满足ans>mid（即未完全覆盖），0反之
    double maxx_covered_right=0;
    for(int i=1;i<=n;i++){
        double del=sqrt(mid*mid-1.0*y[i]*y[i]);//勾股定理（八年级上）
        if(x[i]-del<=maxx_covered_right&&x[i]+del>=maxx_covered_right)//垂径定理（九年级下）
        maxx_covered_right=x[i]+del;
    }
    return maxx_covered_right<l;
}
int main(){
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
    double lef=0,rig=1414213562.374,mid;
    while(rig-lef>=eps){
        mid=(lef+rig)/2;
        if(check(mid))lef=mid;
        else rig=mid;
    }
    printf("%.5lf",lef);
    return 0;
}

慢！

代码中还有两处解释一下。

rig=1414213562.374 这是什么鬼？

这里@_lyx1311 大佬提到了最大答案可能是 \sqrt2\times 10^9，详见这里。

const double eps=0.0003; 数值有什么讲究吗？

没有，但是设置得太大会 WA，太小会 TLE（时限只有 600ms），所以折中取 0.0003。