CF1059D题解
Grisses
·
·
题解
题面
求一个能覆盖所有点的与 y 轴相切的最小的圆。
对于所有的点，如果它们同时出现在 y 轴的上下，输出 -1。
然后，我们二分枚举圆的半径。
如果半径为 r，
$DJ=JE=\sqrt{r\times r-X_A\times X_A}$。
我们只需枚举每一个点在半径为 $r$ 时的 $D,E$ 坐标，到最后如果还满足 $\max\limits_{i=1}^nX_D\le \min\limits_{i=1}^nX_E$ 就说明半径为 $r$ 是成立的。
代码：
```cpp
#include<bits/stdc++.h>
#define db long double
using namespace std;
int n;
struct node{
int x,y;
}a[100005];//储存点的坐标
bool ch(db x){
db maxl=-1e15,minr=1e15;//初始化左右端点
for(int i=1;i<=n;i++){
db c,d;
if(x*x<(a[i].y-x)*(a[i].y-x))return 0;//无法与y轴相切
c=a[i].x-sqrt(x*x-(a[i].y-x)*(a[i].y-x));
d=a[i].x+sqrt(x*x-(a[i].y-x)*(a[i].y-x));
maxl=max(maxl,c);
minr=min(minr,d);//更新
}
return maxl<=minr;
}
int main()
{
scanf("%d",&n);
bool f1,f2;
f1=f2=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
if(a[i].y>0)f1=1;
if(a[i].y<0)f2=1;
a[i].y=abs(a[i].y);//取绝对值方便处理
}
if(f1&&f2){//y轴上下都有点
printf("-1");
return 0;
}
int T=1000;//防止死循环（血与泪的教训）
db l=0,r=1e14+10,mid;
while(T--){
mid=(l+r)/2;
if(ch(mid))r=mid;
else l=mid;//二分
}
printf("%.6Lf",r);
return 0;
}
```