🧩 问题转化：从椭圆到圆

题目要求用一个椭圆覆盖所有点，其半短轴长最小。关键在于：

• 椭圆长轴方向固定（由增幅方向 $a$ 决定）
• 长轴长度是短轴的 $p$ 倍

我们可以通过两步坐标变换，将这个椭圆问题等价为一个最小圆覆盖问题：

1. 旋转坐标系：将整个坐标系绕原点顺时针旋转 $a$ 度，让椭圆的長轴与$x$轴平行。
2. 缩放横坐标：将变换后所有点的 $x$ 坐标除以 $p$，将椭圆“压扁”回圆形。

经过这两步变换，原问题就转化为：在变换后的新坐标系下，找一个能覆盖所有点的最小圆。这个最小圆的半径，就是原问题中椭圆的半短轴长。

📐 关键算法：最小圆覆盖

求解最小圆覆盖，常用一种随机增量算法，其核心思想是：

• 随机打乱点的顺序。
• 逐点扩展，维护当前的最小覆盖圆：
  1. 初始圆可以设为以第一个点为圆心，半径为0。
  2. 当遍历到第 $i$ 个点 $P_i$ 时：
     • 如果 $P_i$ 在当前圆内，则继续。
     • 如果 $P_i$ 在当前圆外，则：
       • 设置新圆为以 $P_i$ 为圆心，半径为0的圆，并将前 $i-1$ 个点中的第一个点 $P_j$ ( $j < i$ ) 加入：
         • 如果 $P_j$ 在新圆外，则更新圆的直径为 $P_iP_j$ 为直径的圆，并将前 $j-1$ 个点中的第一个点 $P_k$ ( $k < j$ ) 加入：
           • 如果 $P_k$ 在当前的圆外，则这三点 $P_i, P_j, P_k$ 确定一个圆（即三角形的外接圆）。

这个算法的时间复杂度平均为 $O(n)$，能够处理 $n \leq 50000$ 的规模。

🧮 坐标变换的数学细节

假设原坐标系中点坐标为 $(x, y)$，增幅方向角度为 $a$（从 $x$ 正方向逆时针转），放大倍数为 $p$。

1. 旋转（顺时针旋转 $a$ 度，注意是顺时针，所以旋转角取负值）： 旋转后的坐标 $(x', y')$ 为：

   $$\begin{aligned} x' &= x \cos(-a) - y \sin(-a) = x \cos a + y \sin a \\ y' &= x \sin(-a) + y \cos(-a) = -x \sin a + y \cos a \end{aligned} $$

   需要注意的是，根据中的代码实现，其旋转公式为：

   p[i].x = (x0 * cosa + y0 * sina ) / (a * 1.0); // 注意这里除以了放大倍数p，实际合并了缩放步骤
   p[i].y = (y0 * cosa - x0 * sina);
   

   这里可以理解为先进行了旋转（x0 * cosa + y0 * sina 和 y0 * cosa - x0 * sina），然后直接对旋转后的横坐标进行了缩放（除以p）。

2. 缩放：将旋转后的 $x'$ 坐标除以 $p$，得到最终用于最小圆覆盖算法的坐标 $(x'' , y'')$：

   $$\begin{aligned} x'' &= \frac{x'}{p} = \frac{x \cos a + y \sin a}{p} \\ y'' &= y' = -x \sin a + y \cos a \end{aligned} $$

⚙️ 核心代码实现

以下是基于实现的最小圆覆盖核心部分，使用了随机增量算法：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <random>

using namespace std;

struct Point {
    double x, y;
};

// 计算两点距离的平方
double dist2(const Point& a, const Point& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return dx * dx + dy * dy;
}

// 求外接圆圆心
Point circle_center(const Point& A, const Point& B, const Point& C) {
    double a = B.x - A.x, b = B.y - A.y;
    double c = C.x - A.x, d = C.y - A.y;
    double e = a * (A.x + B.x) + b * (A.y + B.y);
    double f = c * (A.x + C.x) + d * (A.y + C.y);
    double g = 2.0 * (a * (C.y - B.y) - b * (C.x - B.x));
    
    if (fabs(g) < 1e-10) { // 处理三点共线情况
        // 返回距离最远两点的中点
        double dAB = dist2(A, B), dAC = dist2(A, C), dBC = dist2(B, C);
        if (dAB >= dAC && dAB >= dBC) return {(A.x + B.x) * 0.5, (A.y + B.y) * 0.5};
        if (dAC >= dAB && dAC >= dBC) return {(A.x + C.x) * 0.5, (A.y + C.y) * 0.5};
        return {(B.x + C.x) * 0.5, (B.y + C.y) * 0.5};
    }
    
    Point center;
    center.x = (d * e - b * f) / g;
    center.y = (a * f - c * e) / g;
    return center;
}

// 最小圆覆盖
double min_circle_cover(vector<Point>& points) {
    if (points.empty()) return 0;
    if (points.size() == 1) return 0;
    
    // 随机打乱点集，保证期望线性复杂度 
    shuffle(points.begin(), points.end(), mt19937(random_device()()));
    
    Point center = points[0];
    double radius2 = 0; // 半径的平方
    
    for (int i = 1; i < points.size(); i++) {
        if (dist2(points[i], center) > radius2 + 1e-9) {
            // 点i在圆外，设置为新圆心
            center = points[i];
            radius2 = 0;
            
            for (int j = 0; j < i; j++) {
                if (dist2(points[j], center) > radius2 + 1e-9) {
                    // 两点确定一个圆
                    center.x = (points[i].x + points[j].x) * 0.5;
                    center.y = (points[i].y + points[j].y) * 0.5;
                    radius2 = dist2(points[i], center);
                    
                    for (int k = 0; k < j; k++) {
                        if (dist2(points[k], center) > radius2 + 1e-9) {
                            // 三点确定一个圆
                            center = circle_center(points[i], points[j], points[k]);
                            radius2 = dist2(points[i], center);
                        }
                    }
                }
            }
        }
    }
    
    return sqrt(radius2);
}

💡 注意事项与优化

1. 精度处理：计算过程中注意使用 double 类型，比较时使用适当的容差值（如 1e-9）。
2. 随机化：点集的随机打乱对保证算法效率很重要。
3. 边界情况：注意处理点集为空、只有一个点、两个点、三点共线等情况。
4. 复杂度：该随机增量算法的期望时间复杂度为 $O(n)$，最坏情况下（如点按某种特殊顺序排列）可能达到 $O(n^3)$，但通过随机打乱点集可以有效避免。

💎 总结

解决「SHOI2014」信号增幅仪问题的步骤清晰：

1. 坐标变换：通过旋转和缩放，将椭圆覆盖问题转化为标准的最小圆覆盖问题。
2. 算法求解：使用随机增量算法求解最小圆覆盖，得到半径即为所求的半短轴长。
3. 输出结果：将计算得到的半径四舍五入到三位小数。