CodeForces|Nature Reserve(Codeforces Round #514 (Div. 2)-1060E)(三分答案,数学) CodeForces|数学

文章目录

前言
题目
思路
代码

前言这种题没做过,但考试时想得差不多了…
题目 CF传送门
题目大意
现在有n个点,坐标分别为 ( x i , y i ) (x_i,y_i) (xi?,yi?),现在求一个最小半径的圆,使得包含所有点且和 x x x轴相切(只有一个交点),
若不存在,输出-1
答案精确到 1 0 ? 6 10^{-6} 10?6
? 1 0 7 < = x i , y i < = 1 0 7 , y i ! = 0 -10^7< =x_i,y_i< =10^7,y_i!=0 ?107<=xi?,yi?<=107,yi?!=0
i n p u t input input

1 0 1

o u t p u t output output

0.5

i n p u t input input

3 0 1 0 2 0 -3

【CodeForces|Nature Reserve(Codeforces Round #514 (Div. 2)-1060E)(三分答案,数学)】 o u t p u t output output

-1

i n p u t input input

2 0 1 1 1

o u t p u t output output

0.625

思路首先,我们知道，只要x轴两侧各有点,则输出-1.
我们记圆心为 ( X , r ) (X,r) (X,r)由于和x轴相切,则半径为r，对于每一个点 ( x i , y i ) (x_i,y_i) (xi?,yi?)

CodeForces|Nature Reserve(Codeforces Round #514 (Div. 2)-1060E)(三分答案,数学)

文章图片

都有:
( X ? x i ) 2 + ( r ? y i ) 2 < = r 2 (X-x_i)^2+(r-y_i)^2< =r^2 (X?xi?)2+(r?yi?)2<=r2
我们只能从化简式子入手了:
X 2 ? 2 x i X + x i 2 + r 2 ? 2 r y i + y i 2 < = r 2 X^2-2x_iX+{x_i}^2+r^2-2ry_i+{y_i}^2< =r^2 X2?2xi?X+xi?2+r2?2ryi?+yi?2<=r2
化简一下,把r移到左边:
X 2 ? 2 x i X + x i 2 + y i 2 2 y i < = r \frac{X^2-2x_iX+{x_i}^2+{y_i}^2}{2y_i}< =r 2yi?X2?2xi?X+xi?2+yi?2?<=r
也就是说,如果我们有确定的 X X X，那么:
r = m a x { ( X ? x i ) 2 + y i 2 2 y i } r=max\{\frac{(X-x_i)^2+{y_i}^2}{2y_i}\} r=max{2yi?(X?xi?)2+yi?2?},我们就有确定的 r r r
我们又发现,对于答案所在的X，在它左右走 r r r都会单调递增,形成形状像山谷的形状,那么直接三分 X X X找谷底即可
代码

#include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; LL read(){ LL f=1,x=0; char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1; s=getchar(); } while(s>='0'&&s<='9'){x=x*10+s-'0'; s=getchar(); } return x*f; } #define eps 1e-8 #define MAXN 100000 #define INF 0x3f3f3f3f #define Mod int(1e9+7) int n; LL x[MAXN+5],y[MAXN+5]; double check(double X){ double r=0; //半径计算 for(int i=1; i<=n; i++) r=max(r,((X-x[i])*(X-x[i])+y[i]*y[i])/(2.0*y[i])); return r; } int main(){ int f=0; n=read(); for(int i=1; i<=n; i++){ x[i]=read(),y[i]=read(); if(y[i]<0) y[i]=-y[i],f|=1; else f|=2; } if(f==3){ puts("-1"); return 0; } double L=-1e7-2,R=1e7+2; while(L+epstmp2) L=Mid1; //左边半径较大,L右移动 else R=Mid2; } printf("%.10lf\n",check(L)); return 0; }