题意分析

这道题目要求我们找到给定平面点集中三个点构成的三角形，使得该三角形的外接圆半径最大，并输出这个最大半径（保留3位小数）。

关键点：

1. 输入：多个测试用例，每个用例给出若干点的坐标（x, y）。
2. 输出：对于每个测试用例，输出所有可能三角形外接圆半径的最大值。
3. 外接圆半径公式：
   • 给定三角形三点 A, B, C，其外接圆半径 R 的计算公式为： [ R = \frac{a \cdot b \cdot c}{4 \cdot S} ] 其中：
     • a, b, c 是三角形边长
     • S 是三角形面积（可用叉积计算）

解题思路

1. 暴力枚举所有可能的三角形：

   • 由于 n ≤ 655，直接三重循环遍历所有 C(n, 3) 种组合是可行的（时间复杂度 O(n³)）。
   • 对于每个三角形，计算其外接圆半径，并维护最大值。

2. 优化计算：

   • 预处理点对距离：先计算所有点两两之间的距离，避免重复计算。
   • 叉积计算面积：用叉积计算三角形面积，避免海伦公式的精度问题。

3. 外接圆半径计算：

   • 使用公式： [ R = \frac{AB \cdot BC \cdot CA}{4 \cdot |(B-A) \times (C-A)|} ] 其中 × 表示叉积。

代码示例

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
using namespace std;

const int maxN = 700; // 最大点数
double dis[maxN][maxN]; // 存储点i和点j之间的距离
double x[maxN], y[maxN]; // 存储所有点的坐标

// 计算二维叉积 (x1,y1) × (x2,y2) = x1*y2 - x2*y1
double cross(double x1, double y1, double x2, double y2) {
    return x1 * y2 - x2 * y1;
}

int main() {
    int cases;
    scanf("%d", &cases); // 读取测试用例数量
    while (cases--) {
        int n;
        double ans = 0.0; // 存储最大半径
        scanf("%d", &n); // 读取点数n
        for (int i = 0; i < n; ++i)
            scanf("%lf%lf", &x[i], &y[i]); // 读取所有点的坐标

        // 预处理所有点对之间的距离
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j) {
                double dx = x[i] - x[j];
                double dy = y[i] - y[j];
                dis[i][j] = dis[j][i] = sqrt(dx * dx + dy * dy); // 计算欧几里得距离
            }

        // 枚举所有可能的三角形 (i,j,k)
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                for (int k = j + 1; k < n; ++k) {
                    // 计算叉积（三角形面积的2倍）
                    double t = fabs(cross(x[k] - x[i], y[k] - y[i], x[j] - x[i], y[j] - y[i]));
                    // 计算外接圆半径 R = (AB * BC * CA) / (4 * S)
                    // 这里 AB = dis[i][j], BC = dis[j][k], CA = dis[k][i]
                    // S = t / 2.0
                    // 所以 R = (dis[i][j] * dis[j][k] * dis[k][i]) / (2.0 * t)
                    ans = max(ans, dis[i][j] * dis[j][k] * dis[k][i] / (2.0 * t));
                }
        printf("%.3lf\n", ans); // 输出结果，保留3位小数
    }
    return 0;
}

代码解析

1. 预处理点对距离：

   • dis[i][j] 存储点 i 和点 j 的距离，避免重复计算。

2. 三重循环枚举三角形：

   • i, j, k 遍历所有可能的三角形组合，确保 i < j < k 避免重复计算。

3. 叉积计算面积：

   • cross(x[k] - x[i], y[k] - y[i], x[j] - x[i], y[j] - y[i]) 计算向量 (A→C) × (A→B)，即三角形面积的2倍。

4. 外接圆半径计算：

   • 使用公式 R = (AB * BC * CA) / (4 * S)，其中 S = t / 2.0。

5. 输出结果：

   • 保留3位小数，符合题目要求。

复杂度分析

• 时间复杂度：O(n³)，适用于 n ≤ 655（最坏情况约 655³ ≈ 2.8e8 次运算，现代计算机可接受）。
• 空间复杂度：O(n²)，用于存储点对距离。