自动搬运

查看原文

来自洛谷，原作者为

	Raymondzll **

搬运于2025-08-24 22:28:04，当前版本为作者最后更新于2022-01-17 18:03:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$。