题目链接

【模板】最小圆覆盖Ⅰ ‖ 小范围

思路

本题正确思路为计算几何的思路（我还没学）

这里提供一个三分的思路（我和Deepseek大战了1周才AC的）：

首先，在外层对x三分，然后对于确定的x，在内层对y进行嵌套三分

（思路本身不难，难在代码实现）

AC代码

#include <iomanip>  // setprecision
#include <iostream>
#include <cmath>
using namespace std;
using ld = long double;  // 使用double就WA，我也不知道为什么

const int N = 2e3;
const ld eps = 1e-12;  // eps >= 1e-11就WA，我也不知道为什么
ld xarr[N+10], yarr[N+10];
int n;

ld func(ld nowx, ld nowy)
{
    ld ret = 0;
    for(int i = 1; i <= n; i ++ ){
        ld dx = nowx - xarr[i], dy = nowy - yarr[i];
        ret = max(ret, dx*dx + dy*dy);
        // ds教的：最后再使用sqrt，从而减小sqrt精度对判断的影响
        //（但是我发现这里使用sqrt好像对最终结果没什么影响）
    } 
    return sqrt(ret);
}

// 三分思想很简单，雨巨姐姐讲得很清楚了，这里我就不赘述了，不懂的自己看课去
ld inner3div(ld x, ld lty, ld rty, ld& resy)
{
    while( rty - lty > eps ){
        ld dy = (rty - lty) / 3.0;
        ld midy1 = lty + dy, midy2 = rty - dy;
        if( func(x, midy1) > func(x, midy2) ) lty = midy1;
        else rty = midy2;
    }
    resy = (lty + rty) / 2.0;  // ds教的
    return func(x, resy);
}

ld outer3div(ld ltx, ld rtx, ld& resx, ld& resy)
{
    while( rtx - ltx > eps ){
        ld dx = (rtx - ltx) / 3.0;
        ld midx1 = ltx + dx, midx2 = rtx - dx;
        if( inner3div(midx1, -1e4, 1e4, resy) > inner3div(midx2, -1e4, 1e4, resy) )
            // 这里的resy仅仅是传参需要
            ltx = midx1;
        else rtx = midx2;
    }
    resx = (ltx + rtx) / 2.0;
    ld ret = inner3div(resx, -1e4, 1e4, resy);  // 这里的resy才是真正的结果
    return ret;
}

int main()
{
    cin >> n;
    for( int i = 1; i <= n; i ++ ) cin >> xarr[i] >> yarr[i];
    ld resx, resy;
    ld dis = outer3div(-1e4, 1e4, resx, resy);
    cout << fixed << setprecision(12) << dis << '\n' << resx << ' ' << resy;
    return 0;
}

PS一下

这个题三分太难做了，完全不建议使用三分

同时这个题三分的数据限制得有点紧。我做了以下测试：

1. double 或者 long double
2. eps数据范围

结果发现，只有使用long double并且数据范围为eps <= 1e-12的时候才能AC，而且这种情况下用时不到1秒

ds指出我的代码外层三分写错了，但是ds自己生成的代码就有问题。所以各位大佬，走过路过的帮忙看一眼我的三分有没有问题，求求啦

这个题放在 二分、三分、01分数规划 这一讲里面作为三分例题真是拉完了，完全不如后面那道急速行走题目