P4699 防护伞（【基础】）

解题思路

伞心必须放在某一个黑子上。对每个黑子，把它当成圆心，计算它到所有黑子的最大距离的平方，这个最大值就是罩住全部黑子所需的半径平方。遍历所有黑子当圆心，取半径平方最小的那一个，再用面积公式算伞的面积。下面分四步实现。

**第一步，读入。**读入 n 和 n 个黑子的坐标，分别存进 coordX、coordY 数组。

**第二步，枚举圆心。**对每个黑子 i 当圆心，两重循环计算它到其他所有黑子 j 的距离平方 distSq = dx×dx + dy×dy（dx、dy 是两个坐标的差），取其中的最大值 maxDistSq。这个值就是以 i 为圆心罩住所有点的最小半径平方。

**第三步，取最优圆心。**在所有黑子里，取 maxDistSq 最小的那个作为 bestDistSq。注意第一个黑子要先把 bestDistSq 设成它的 maxDistSq，再和后面的比较。

**第四步，算面积。**面积 = π × 半径²，其中半径 = sqrt(bestDistSq)，π 取 3.1415926535，输出保留 4 位小数，用 fixed + setprecision(4)。

注意：黑子坐标可能达到 10 亿级别，两个点距离的平方会非常大，所以一定要用 long long 来存，防止溢出；最终面积用 double 计算即可。

参考代码

// P4699 防护伞：把伞心定在某个黑子上，求能罩住所有黑子的最小圆面积
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long coordX[1005], coordY[1005];
    for (int i = 0; i < n; i++) cin >> coordX[i] >> coordY[i];
    // 对每个黑子作为圆心，计算到所有点的最大距离平方，取其中的最小值
    long long bestDistSq = 0;
    for (int i = 0; i < n; i++) {
        long long maxDistSq = 0;
        for (int j = 0; j < n; j++) {
            long long dx = coordX[i] - coordX[j];
            long long dy = coordY[i] - coordY[j];
            long long distSq = dx * dx + dy * dy;
            if (distSq > maxDistSq) maxDistSq = distSq;
        }
        if (i == 0 || maxDistSq < bestDistSq) bestDistSq = maxDistSq;
    }
    // 半径取sqrt(bestDistSq)，面积=3.1415926535*半径²，保留4位小数
    double radius = sqrt((double)bestDistSq);
    double area = 3.1415926535 * radius * radius;
    cout << fixed << setprecision(4) << area << endl;
    return 0;
}

复杂度分析

对每个黑子都要计算它到其余所有黑子的距离，时间复杂度 O(N²)。N 最大几百，完全没问题。空间上只需要存每个点的坐标，是 O(N)。