感谢审核人
Description
给定 \(n\) 个点，椭圆长轴的方向 \(a\) 和放大倍数 \(p\)，求覆盖全部点的最小椭圆的半短轴长度。
Solution
让我们求最小覆盖椭圆，但是椭圆不具有什么好的性质，我们可以把椭圆转化成圆来做，这样，题目就转化成了最小覆盖圆，这个用随机增量法来做就可以了。
接下来我们考虑如何转化成圆。
首先从长轴方向 \(a\) 入手，因为斜着求椭圆显然很麻烦，我们可以把它旋转到 \(x\) 轴的方向，将 \(x\) 轴逆时针旋转 \(a\) 度与长轴重合显然也很麻烦，我们考虑等价操作：逆时针旋转坐标轴 \(a\) 度，就等于顺时针旋转每个点 \(a\) 度，因为本题只考虑半短轴的长度，所以坐标位置不用考虑，因此这两个操作等价。
接下来考虑怎么把椭圆转换成圆，这个相对来说好想一点，因为题目中扩大了 \(x\) 坐标 \(p\) 倍，所以说我们只需要把每个点的横坐标变成原来的 \(\frac{1}{p}\) 即可，这样我们就把一个椭圆转化成圆了。
最后套一个随机增量法求最小圆覆盖即可。不会的可以看看这一道题。
Code
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 5e4 + 5;
const double eps = 1e-6;
const double Pi = acos(-1.0);
using namespace std;
struct Point{
double x,y;
}p[N];
struct Circle{
Point p; double r;
}C;
struct Line{
Point s,t;
}u,v;
int n; double a,b;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
Point operator +(Point a,Point b) { return Point{a.x+b.x,a.y+b.y}; }//加
Point operator -(Point a,Point b) { return Point{a.x-b.x,a.y-b.y}; }//减
Point operator *(Point a,double t) { return Point{t * a.x,t * a.y}; }//数乘
Point operator /(Point a,double t) { return Point{a.x / t,a.y / t}; }//数除
il double operator *(Point a,Point b) { return a.x*b.y - a.y*b.x; }//叉积
il double operator &(Point a,Point b) { return a.x*b.x + a.y*b.y; }//点积
il double dis(Point a,Point b) { return sqrt((b-a)&(b-a)); }
Point GetNode(Point a,Point u,Point b,Point v)//求交点
{
double t = (a-b)*v / (v*u);
return a + u*t;
}
Point rotate(Point a,double b) { return Point{a.x*cos(b)-a.y*sin(b),a.y*cos(b)+a.x*sin(b)}; }
Line Midperp(Point a,Point b) { return Line{(a+b)/2,rotate(b-a,Pi/2)}; }//找中垂线
Circle cover(Point a,Point b) { return Circle{(a+b)/2,dis(a,b)/2}; }//覆盖两个点的最小圆就在他俩中点上
Circle cover(Point a,Point b,Point c)//三个点的圆，找中垂线的交点，即为答案
{
u = Midperp(a,b) , v = Midperp(a,c);
Point p = GetNode(u.s,u.t,v.s,v.t);
return Circle{p,dis(p,a)};
}
il void Random_Increment()
{
C = {p[1] , 0};
for(re int i=2;i<=n;i++)
{
if(C.r < dis(C.p,p[i]))
{
C = {p[i] , 0};//一点圆
for(re int j=1;j<i;j++)
{
if(C.r < dis(C.p,p[j]))//两点圆
{
C = cover(p[i],p[j]);
for(re int k=1;k<j;k++)
{
if(C.r < dis(C.p,p[k]))//三点确定一个圆，可以证明这个复杂度是均摊O(n)的
C = cover(p[i],p[j],p[k]);
}
}
}
}
}
}
signed main()
{
n = read();
for(re int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
scanf("%lf%lf",&a,&b);
for(re int i=1;i<=n;i++)
{
p[i] = rotate(p[i],-a/180*Pi);
p[i].x /= b;
}
random_shuffle(p+1,p+n+1);//随机打乱，保证复杂度
Random_Increment();
printf("%.3lf",C.r);
return 0;
}
复杂度 \(O(n)\)，可以通过本题。