CF1059D Nature Reserve

原题链接

网络不好的可以到洛谷上去QwQ

题目大意

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

输入输出样例

输入：

2

0 1

1 1

输出

0.625

感觉最多是蓝题难度?

首先无解的情况很简单，如果存在一个点使得它与其他点相对于\(x\)轴不同侧，就无解（显然）。考虑到半径不好直接确定，我们二分一下。然后就是怎么\(check\)的问题了。为了方便，我们假设所有的点都在\(x\)轴上方。

假设此时二分的值为\(mid\)，左右端点分别为\(l,r\)，那么圆心一定在\(y=mid\)这条直线上。对于某个确定的点，因为它能被覆盖，且半径和圆心的纵坐标已知，所以可以确定圆心横坐标的取值区间（如果它到\(y=mid\)的距离超过\(mid\)的话就可以直接让\(check\)返回\(0\)了）。所以我们考虑取所有点对应的取值区间的交集，如果交集非空，就让\(check\)返回\(1\)，缩小\(r\)的范围，否则增大\(l\)的范围。这样就可以了。

虽然题目要求的误差范围是\(10^{-6}\)，但不知道为什么这样写会T：

while((r-l) > 1e-6) {

    mid = (l+r)/2.0;

    if(check(mid)) r = mid;

    else l = mid;

}

于是我就改成了这样：

int t = 0;

while(t++ <= 210) {

    mid = (l+r)/2.0;

    if(check(mid)) r = mid;

    else l = mid;

}

就A了。其中的原因，我无法明白，望诸君指教。

AC代码：

#include <bits/stdc++.h>

using namespace std;

const long double EPS = 0.00000001;

const int N = 100000;

int n;

struct Node {

    long long x, y;

}nodes[N+5];

template <typename T>

T Abs(T x) { return x >= 0 ? x : -x; }

template <typename T>

T Max(T x, T y) { return x > y ? x : y; }

template <typename T>

T Min(T x, T y) { return x > y ? y : x; }

double disX(int y, double r) {

    return sqrtl(-1.0*y*y+2.0*r*Abs(y));

}

int check(double x) {

	if(Abs(nodes[1].y)-x > x) return 0;

	if(x-Abs(nodes[1].y) < -x) return 1;

    double l1, r1, l = nodes[1].x-disX(nodes[1].y, x), r = nodes[1].x+disX(nodes[1].y, x);

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

    	if(Abs(nodes[i].y)-x > x) return 0;

		if(x-Abs(nodes[i].y) > x) return 1;

        l1 = nodes[i].x-disX(nodes[i].y, x), r1 = nodes[i].x+disX(nodes[i].y, x);

        l = Max(l1, l), r = Min(r1, r);

    }

    return l <= r;

}

int main() {

    scanf("%d", &n);

    int dir = 0;

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

        scanf("%I64d%I64d", &nodes[i].x, &nodes[i].y);

        if(!dir && nodes[i].y != 0) dir = (nodes[i].y > 0 ? 1 : -1);

        if(nodes[i].y != 0)

            if((dir == 1 && nodes[i].y < 0) || (dir == -1 && nodes[i].y > 0)) {

                printf("-1\n");

                return 0;

            }

    }

    double l = 0, r = 1e17, mid = r;

    int t = 0;

    while(t++ <= 210) {

        mid = (l+r)/2.0;

        if(check(mid)) r = mid;

        else l = mid;

    }

    printf("%.8lf\n", mid);

    return 0;

}

给一组数据：

输入：

4

-10000000 1

10000000 1

-10000000 10000000

10000000 10000000

输出：

50000000000000.4921875

巴特西

CF1059D Nature Reserve

题目大意

输入输出样例

最新文章

热门文章