P4288 [SHOI2014]信号增幅仪 题解

感谢审核人

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)\)，可以通过本题。