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

前言

这种题没做过,但考试时想得差不多了…

题目

CF传送门
题目大意
现在有n个点,坐标分别为$(x_i,y_i)$,现在求一个最小半径的圆,使得包含所有点且和$x$轴相切(只有一个交点),
若不存在,输出-1
答案精确到$10^{?6}$
$?10^7<=x_i,y_i<=10^7,y_i!=0$
$input$

1 0 1 

$output$

0.5 

$input$

3 0 1 0 2 0 -3 

$output$

-1 

$input$

2 0 1 1 1 

$output$

0.625 

思路

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

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

代码

#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<climits> #include<cstring> #include<iostream> #include<algorithm> #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+eps<R){
     //三分横坐标double Mid1=L+(R-L)/3,Mid2=R-(R-L)/3;double tmp1=check(Mid1),tmp2=check(Mid2);if(tmp1>tmp2) L=Mid1;//左边半径较大,L右移动else R=Mid2;}printf("%.10lf\n",check(L));return 0; }