BalticOI2012 移动网络
Azazеl
·
·
题解
2022.11.8 Update
#### 题意
> $~~~~$ 有一条从 $(0,0)$ 到 $(0,l)$ 的线段与 $n$ 个点，找到线段上的一个点使其离平面给定的所有点最小距离最大。求这个最大距离。
> $~~~~$ $1\leq n \leq 10^6
题意
$~~~~$ 对于某个二分的距离，则当线段能被 所有平面上的点以该距离作圆覆盖时 该距离是合法的。由圆方程可以解出一个圆心为 $(x,y)$ ，半径为 $r$ 的圆与 $x$ 轴的交点横坐标为 $\pm\sqrt{r^2-y^2}+x$ 。
$~~~~$ 按照正常思路我们就需要对区间进行排序然后 $O(n)$ 判定是否能覆盖整条线段，但这样复杂度就达到了 $\mathcal{O(n \log \dfrac{\sqrt{5}l}{\epsilon}\log n)}$ ，再考虑时限比较紧，显然需要优化。
$~~~~$ 细想发现我们还有给定的坐标横坐标、纵坐标依次递增的性质没用到。若依次考虑，当 $x$ 相同时，显然 $|y|$ 最小的那个点最可能更新覆盖区间的右端点。然后考虑横坐标不同的三个点 $p_1,p_2,p_3$ ，如果 $p_1$ 与 $p_2$ 画出的圆没有相交，但与 $p_3$ 画出的圆相交，则显然 $p_3$ 的右端点也会比 $p_2$ 的右端点更靠右，也就是 $p_3$ 更新的区间会比 $p_2$ 更优，因此不用排序也是正确的。因此我们就去掉了 $\log n$ 的复杂度。
#### 代码
```cpp
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,L;
int X[1000005],Y[1000005];
bool check(double r)
{
double x=0,From,To;
for(int i=1;i<=n;i++)
{
From=-sqrt(1.0*r*r-1.0*Y[i]*Y[i])+X[i];
To=sqrt(1.0*r*r-1.0*Y[i]*Y[i])+X[i];
if(From<=x&&x<=To) x=To;
}
return x>=L;
}
int main() {
scanf("%d %d",&n,&L);
for(int i=1;i<=n;i++) scanf("%d %d",&X[i],&Y[i]);
double l=0,r=2236068000,mid,Ans;
while(r-l>0.0005)
{
mid=(l+r)/2;
if(check(mid)) r=mid,Ans=mid;
else l=mid;
}
printf("%.6f",Ans);
return 0;
}
```