CF1059D Nature Reserve（二分）

简洁翻译：

有N个点，求与y=0相切的，包含这N个点的最小圆的半径

题解

二分半径右端点开小了结果交了二十几次都没A……mmp……

考虑一下，显然这个半径是可以二分的

再考虑一下，如果所有点都在y轴同一侧就有解，否则肯定无解

然后现在只要考虑在y轴同一侧时某一个半径是否能够包含所有点即可

因为得和y轴相切，所以半径确定时，圆心的y坐标是确定的

然后我们考虑对于每一个点，圆心的x坐标必须处在什么范围内

设这个点坐标为（x,y），圆半径为r，如果y>2*r显然不行

然后用勾股定理算一下两点之间的x坐标最多相差多少，那么就可以知道圆心的x坐标在什么范围内了

然后所有的范围并起来，如果是空集不可行，否则可行

然后注意判断x坐标相差多少时候的写法……代码里写了……

 1 //minamoto
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
 5 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
 6 const int N=2e5+5;
 7 int n,flag1=0,flag2=0;double l=0,r=1e18,ans=0,mx,x[N],y[N];
 8 bool check(double mid){
 9     double L=-1e18,R=1e18;
10     for(int i=1;i<=n;++i){
11         if(2*mid<y[i]) return false;
12         double len=sqrt(mid-(mid-y[i]))*sqrt(mid+(mid-y[i]));
13         //这里判断往左右能延伸多少时要这样写
14         //据说不这样写会导致严重的精度误差
15         //所以要先开方再相乘 
16         L=max(L,x[i]-len),R=min(R,x[i]+len);
17     }
18     return L<R;
19 }
20 int main(){
21     cin>>n;
22     for(int i=1;i<=n;++i){
23         cin>>x[i]>>y[i];
24         if(y[i]>0) flag1=1;
25         if(y[i]<0) flag2=1;
26     }
27     if(flag1&&flag2) return puts("-1"),0;
28     if(flag2){
29         for(int i=1;i<=n;++i) y[i]=-y[i];
30     }
31     int times=500;
32     while(times--){
33         double mid=(l+r)/2;
34         if(check(mid)) ans=mid,r=mid;
35         else l=mid;
36     }
37     printf("%.10lf
",ans);
38     return 0;
39 }

CF1059D Nature Reserve（二分）

相关推荐