ZigZagK的博客
[二分]Codeforces1059D【Nature Reserve】题解
2018年10月8日 21:30
查看标签

题目概述

求一个半径最小的圆使得和 $x$ 轴相切,并且包含了所有给定的点。

解题报告

很明显可以二分 $r$ ,那么圆心就是 $(x,r)$ ,通过每个点就可以确定 $x$ 的范围,如果 $x$ 有取值那么就验证成功。

因为精度要求 $6$ 位,并且 $r$ 的范围有 $10^{15}$ ,long double精度也不够导致二分停不下来,所以要用奇技淫巧,比如__float128 或者做个 $100$ 次就停止。亲测都可过……

示例程序

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long double DB;
const int maxn=100000;

int n,x[maxn+5],y[maxn+5];

inline int fcmp(const DB &a,const DB &b) {if (fabs(a-b)<1e-10) return 0;return a<b?-1:1;}
inline bool check(DB r,DB A=-9e18,DB B=9e18){
    for (int i=1;i<=n;i++){
        if (fcmp(r*2*y[i]-(DB)y[i]*y[i],0)<0) return false;
        A=max(A,-sqrt(r*2*y[i]-(DB)y[i]*y[i])+x[i]);B=min(B,sqrt(r*2*y[i]-(DB)y[i]*y[i])+x[i]);
    }return fcmp(A,B)<=0;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);bool A=true,B=true;
    for (int i=1;i<=n;i++) {scanf("%d%d",&x[i],&y[i]);if (y[i]<0) A=false;if (y[i]>0) B=false;}
    if (!A&&!B) return puts("-1"),0;if (B) for (int i=1;i<=n;i++) y[i]=-y[i];
    DB L=0,R=1e15,mid;for (int t=1;t<=100;t++) check(mid=(L+R)/2)?R=mid:L=mid;
    if (!fcmp(R,1e15)) return puts("-1"),0;printf("%.7f\n",(double)R);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!