信号增幅仪问题

解题思路：

本题要求一个能覆盖所有点的椭圆，令这个椭圆的半短轴长最小，并且椭圆的角度 $\theta$ 和长短轴比例 $p$ 都是唯一确定的。其实就是求一个最小覆盖椭圆。

为了方便，我们先将整个坐标系顺时针旋转 $\theta$，然后我们的椭圆就变成水平的了，然后我们令短半轴为 $1$，则长半轴就是 $p$，然后我们只需要将短半轴按比例放大即可。

此时椭圆的方程应该是 $\frac{x^2}{p^2}+\frac{y^2}{1}=1$，那么所有在椭圆里面的点就应该满足 $\frac{x^2}{p^2}+y^2 \leq 1$，然后我们将坐标系进行变换，我们令 $x’=\frac{x}{p},y’=y$，则新坐标系上任意一个点的坐标就从原来的 $(x,y)$ 变成了 $(x’,y’)$，由于原坐标系的任意一个坐标 $(x,y)$ 和新坐标系中的任意一个坐标 $(x’,y’)$ 是一一对应的，所以两个坐标系是等价的，那么此时所有在原坐标系的椭圆里面的点在新坐标系中就应该满足 $x’^2+y’^2\leq 1$，而这个方程就是一个圆的方程。

通过以上变换，我们就从求原坐标系中的最小覆盖椭圆，变成了求新坐标系中的最小覆盖圆，并且由于椭圆的短半轴 $y$ 和圆的半径 $y’$ 是相等的，因此我们如果想求原坐标系中椭圆的最小短半轴，就等价于求心坐标系中圆的最小半径。这样我们就将原问题变成了一个标准的最小圆覆盖问题，就可以用求最小覆盖圆的方法求本题了。

最小覆盖圆的相关概念可参考

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 50010;
const double eps = 1e-12;
const double PI = acos(-1);

struct Circle
{
    PDD p;
    double r;
}; //圆

int n;
PDD q[N]; //存储所有点的坐标

int sign(double x) //符号函数
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

int dcmp(double x, double y) //浮点数比较函数
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}

PDD operator-(PDD a, PDD b) //重载向量减法
{
    return {a.x - b.x, a.y - b.y};
}

PDD operator+(PDD a, PDD b) //重载向量加法
{
    return {a.x + b.x, a.y + b.y};
}

PDD operator*(PDD a, double t) //重载数乘
{
    return {a.x * t, a.y * t};
}

PDD operator/(PDD a, double t) //重载数除
{
    return {a.x / t, a.y / t};
}

double operator*(PDD a, PDD b) //重载叉乘
{
    return a.x * b.y - a.y * b.x;
}

PDD rotate(PDD a, double b) //将向量 a 顺时针旋转 b 弧度
{
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

double get_dist(PDD a, PDD b) //求 a 和 b 的距离
{
    double x = a.x - b.x, y = a.y - b.y;
    return sqrt(x * x + y * y);
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w) //求两个点向式直线的交点
{
    PDD u = p - q;
    double t = (w * u) / (v * w);
    return p + v * t;
}

pair<PDD, PDD> get_line(PDD a, PDD b) //求 ab 的中垂线
{
    return {(a + b) / 2, rotate(b - a, PI / 2)};
}

Circle get_circle(PDD a, PDD b, PDD c) //求 a, b, c 的外接圆
{
    auto u = get_line(a, b), v = get_line(a, c);
    PDD p = get_line_intersection(u.x, u.y, v.x, v.y);
    return {p, get_dist(p, a)};
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
    double a, p;
    scanf("%lf%lf", &a, &p);
    for(int i = 0; i < n; i++)
    {
        q[i] = rotate(q[i], a / 180 * PI); //将坐标系顺时针旋转 a 度
        q[i].x /= p; //将坐标转化成新坐标
    }

    random_shuffle(q, q + n); //将所有点随机化

    Circle c({q[0], 0}); //最开始定义一个覆盖 q[0] 的最小圆
    for(int i = 1; i < n; i++) //枚举第一个点
        if(dcmp(c.r, get_dist(c.p, q[i])) < 0) //如果 q[i] 在圆外
        {
            c = {q[i], 0}; //从小到大枚举 q[i] 在边上的圆
            for(int j = 0; j < i; j++) //枚举第二个点
                if(dcmp(c.r, get_dist(c.p, q[j])) < 0) //如果 q[j] 在圆外
                {
                    c = {(q[i] + q[j]) / 2, get_dist(q[i], q[j]) / 2}; //从小到大枚举 q[i], q[j] 在边上的圆
                    for(int k = 0; k < j; k++) //枚举第三个点
                        if(dcmp(c.r, get_dist(c.p, q[k])) < 0) //如果 q[k] 在圆外
                            c = get_circle(q[i], q[j], q[k]); //圆上三点都找到，三点确定一个圆
                }
        }
    printf("%.3lf\n", c.r); //输出最小覆盖椭圆的短半轴，也就是最小覆盖圆的半径

    return 0;
}