2020牛客寒假算法基础集训营5 B牛牛战队的比赛地 （三分 || 最小圆覆盖）

链接：https://ac.nowcoder.com/acm/contest/3006/B
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

由于牛牛战队经常要外出比赛，因此在全国各地建立了很多训练基地，每一个基地都有一个坐标(x,y)(x,y)(x,y)。

这周末，牛牛队又要出去比赛了，各个比赛的赛点都在xxx轴上。牛牛战队为了方便比赛，想找一个到达训练基地最大距离最小的地方作为比赛地。

这个问题对于牛牛战队太简单了，它就交给了你，你来帮他算一下~

输入描述:

输入数据第一行包含一个整数N(1≤N≤100 000)N(1 \leq N \leq 100\,000)N(1≤N≤100000)，表示牛牛战队训练基地的数量。

接下来NNN行，每行包括222个整数x,y(−10 000≤x,y≤10 000)x,y(-10\,000 \leq x,y \leq 10\,000)x,y(−10000≤x,y≤10000)，表示每一个训练基地的坐标。

输出描述:

输出一个小数，表示选择的比赛地距离各训练基地最大距离的最小值。

如果你的答案是aaa，标准答案是bbb，当∣a−b∣max(1,∣b∣)≤10−4\frac{|a-b|}{max(1,|b|)}\leq 10^{-4}max(1,∣b∣)∣a−b∣​≤10−4时，你的答案将被判定为正确。

示例1

输入

3
0 0
2 0
0 2

输出

2

说明

当在(0,0)(0,0)(0,0)比赛时，到三个训练基地的最大距离是222。可以证明这是最小值。

题意：

给出n个整数点，在x轴上求一点使得该点与已知n个点的最远距离最小

思路：

方法一：经分析最远距离为单峰函数，三分x坐标。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const double eps = 1e-8;
int n;

struct node
{
    int x, y;
}s[N];

double solve(double x0)
{
    double maxx = 0;
    for(int i = 1; i <= n; ++i)
    {
        maxx = max(maxx, 1.0 * sqrt((s[i].x - x0) * (s[i].x - x0) + s[i].y * s[i].y));
    }
    return maxx;
}

int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &s[i].x, &s[i].y);
        }
        double l = -10000.0, r = 10000.0;
        while(r - l > eps)
        {
            double m1 = l + (r - l) / 3.0;
            double m2 = r - (r - l) / 3.0;
            if(solve(m1) > solve(m2))
                l = m1;
            else
                r = m2;
        }
        printf("%.4f\n", solve(l));
    }
    return 0;
}

方法二：将n个点以x轴对称一遍，就成了最小圆覆盖裸题。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int N = 2e5 + 5;

struct node
{
    double x, y;
}p[N];

node c; ///圆心
double r;   ///半径

int sgn(double x)
{
    if (fabs(x) < eps)
        return 0;
    else
        return x < 0 ? -1 : 1;
}

double Distance(node A, node B) ///两点距离
{
    return hypot(A.x - B.x, A.y - B.y); ///hypot(a, b)求以a, b为直角边的直角三角形斜边长
}

///求三角形abc的外接圆圆心
node circle_center(const node a, const node b, const node c)
{
    node center;
    double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;
    double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;
    double d = a1 * b2 - a2 * b1;
    center.x = a.x + (c1 * b2 - c2 * b1) / d;
    center.y = a.y + (a1 * c2 - a2 * c1) / d;
    return center;
}

///求最小圆覆盖，返回圆心c和半径r:
void min_cover_circle(int n)
{
    random_shuffle(p, p + n);             ///打乱所有点
    c = p[0];
    r = 0;                    ///第一个点
    for (int i = 1; i < n; ++i)        ///剩下所有点
    {
        if (sgn(Distance(p[i], c) - r) > 0) ///pi在圆外部
        {
            c = p[i];
            r = 0;                ///将圆心设为pi半径为0
            for (int j = 0; j < i; ++j) ///重新检查前面的点
            {
                if (sgn(Distance(p[j], c) - r) > 0)///两点定圆
                {
                    c.x = (p[i].x + p[j].x) / 2;
                    c.y = (p[i].y + p[j].y) / 2;
                    r = Distance(p[j], c);
                    for (int k = 0; k < j; ++k)
                    {
                        if (sgn(Distance(p[k], c) - r) > 0)
                        {
                            c = circle_center(p[i], p[j], p[k]);
                            r = Distance(p[i], c);
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; ++i)
        {
            scanf("%lf%lf", &p[i].x, &p[i].y);
            p[i + n].y = -1.0 * p[i].y;
            p[i + n].x = p[i].x;
        }
        n *= 2;
        min_cover_circle(n);
        printf("%.4f\n",r);
    }
    return 0;
}