SHOI2014 信号增幅仪（最小圆覆盖）

发表于 |
字数统计: 971字 | 阅读时长 ≈ 5min

【SHOI2014】信号增幅仪

问题描述

无线网络基站在理想状况下有效信号覆盖范围是个圆形。而无线基站的功耗与圆的半径的平方成正比。

现给出平面上若干网络用户的位置,请你选择一个合适的位置建设无线基站….

就在你拿起键盘准备开始敲代码的时候,你的好朋友发明家 SHTSC 突然出现了。SHTSC 刚刚完成了他的新发明——无线信号增幅仪。增幅仪能够在不增加无线基站功耗的前提下,使得有效信号的覆盖范围在某一特定方向上伸长若干倍。即:使用了增幅仪的无线基站覆盖范围是个椭圆,其功耗正比于半短轴长的平方。现给出平面上若干网络用户的位置,请你选择一个合适的位置建设无线基站,并在增幅仪的帮助下使所有的用户都能接收到信号,且无线基站的功耗最小。

注意:由于SHTSC 增幅仪的工作原理依赖地磁场,增幅的方向是恒定的。

输入格式

第一行一个整数:n。平面内的用户个数。

之后的 n 行每行两个整数 x, y,表示一个用户的位置。

第 n+2 行一个整数:a。表示增幅仪的增幅方向,单位是度。表示增幅仪的方向是从 x 正方向逆时针转 a 度。

第 n+3 行一个整数:p。表示增幅仪的放大倍数。

输出格式

输出一行一个实数,为能够覆盖所有用户的最小椭圆的半短轴长,四舍五入到三位小数。

样例输入

2

1 0

-1 0

0

2

样例输出

0.500

提示

对于 100%的数据,$n≤50000,0≤a<180,1≤p≤100,|x|,|y|≤2×10^8$。

一道高中数学题，先旋转一下坐标系，再做一下伸缩变换，于是就变成了一个标准的圆。

于是只要打一个最小圆覆盖的板就行了。

关于最小圆覆盖，就是做三重增量法，详见代码。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define N 55555
using namespace std;
const double eps=1e-10;
const double pi=4.0*atan(1.0);
struct node{double x,y;}P[N],O;
double Sin,Cos,r;
double dis(node a,node b)
{
	double x=a.x-b.x;
	double y=a.y-b.y;
	return sqrt(x*x+y*y);
}
bool Incircle(node p){return r>=dis(O,p);}
void Getcir(node a,node b,node c)
{
	O.y=((b.x-c.x)*(a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)-(a.x-b.x)*(b.x*b.x-c.x*c.x+b.y*b.y-c.y*c.y))/((a.y-b.y)*(b.x-c.x)-(b.y-c.y)*(a.x-b.x))/2.0;
	O.x=(a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)/(a.x-b.x)/2.0-(a.y-b.y)/(a.x-b.x)*O.y;
	r=dis(O,a);
}
int main()
{
	int i,j,k,n;double x,y,a,p;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%lf%lf",&P[i].x,&P[i].y);
	scanf("%lf%lf",&a,&p);a=-a;
	Sin=sin(pi*a/180.0);
	Cos=cos(pi*a/180.0);
	for(i=1;i<=n;i++)
	{
		x=P[i].x;y=P[i].y;
		P[i].x=Cos*x-Sin*y;
		P[i].y=Sin*x+Cos*y;
		P[i].x/=1.0*p;
	}
	random_shuffle(P+1,P+n+1);
	for(i=1;i<=n;i++)
	{
		if(Incircle(P[i]))continue;
		O.x=P[i].x;O.y=P[i].y;r=0;
		for(j=1;j<i;j++)
		{
			if(Incircle(P[j]))continue;
			O.x=(P[i].x+P[j].x)/2.0;
			O.y=(P[i].y+P[j].y)/2.0;
			r=dis(P[i],P[j])/2.0;
			for(k=1;k<j;k++)
			{
				if(Incircle(P[k]))continue;
				Getcir(P[i],P[j],P[k]);
			}
		}
	}
	printf("%.3lf",r);
}