CodeForces - 1059D（二分+误差） - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

链接：CodeForces - 1059D

题意：给出笛卡尔坐标系上 n 个点，求与 x 轴相切且覆盖了所有给出点的圆的最小半径。

题解：二分半径即可。判断：假设当前二分到的半径是 R ，因为要和 x 轴相切，所以圆心一定在 y = R 上，对于每一个点而言，圆要覆盖该点，那么圆心在 y = R 上一定有一段限定区间，所以只要判断这 n 个区间是否有公共区间即可。卡点：误差，太可恶了，求区间段时应该将 sqrt(R * R - d * d) 写成 sqrt(R - d) * sqrt(R + d) ，否则误差特别大。

#include <bits/stdc++.h>

using namespace std;

const double EPS = 1e-;

const double INF = 1e17;

const int mod = 1e9 + ;

const int maxn = 1e5 + ;

int n;

double x[maxn], y[maxn];

bool judge(double R)

{

    double l = -INF, r = INF;

    for(int i = ; i < n; i++){

        double d = fabs(y[i] - R);

        if(d > R) return false;

        //不可以写成sqrt(R * R - d * d),这样误差会加大

        double k = sqrt(R - d) * sqrt(R + d);

        double a = x[i] - k, b = x[i] + k;

        if(a > r || b < l) return false;

        l = max(l, a);

        r = min(r, b);

    }

    return true;

}

bool OK()

{

    bool z = false, f = false;

    for(int i = ; i < n; i++){

        if(y[i] > ) z = true;

        else if(y[i] < ) f = true;

    }

    return !(z && f);

}

int main()

{

    scanf("%d", &n);

    for(int i = ; i < n; i++) scanf("%lf%lf", &x[i], &y[i]);

    if(!OK())return puts("-1") & ;

    for(int i = ; i < n; i++) y[i] = fabs(y[i]);

    double l = , r = INF;

    for(int i = ; i < ; i++){

        double mid = (l + r) / 2.0;

        if(judge(mid)) r = mid;

        else l = mid;

    }

    printf("%.6f\n", r);

    return ;

}