BZOJ 3564

传送门

最小椭圆覆盖是什么东西…只听说过最小圆覆盖啊…

不过这道题似乎把坐标系旋转一下再把$x$轴缩短几倍就成了最小圆覆盖

坐标旋转公式:推导过程戳我

$x’=\cos(\alpha)x-\sin(\alpha)y$

$y’=\cos(\alpha)y+\sin(\alpha)x$

表示$(x,y)$逆时针旋转$\alpha$度之后的坐标$(x’,y’)$,这道题要把旋转过的复原,那就旋转$-\alpha$度

然后$x$坐标再除以放大倍数$d$就好了,下面就是随机增量了,扯点我的理解:

随机增量=随机+增量

每次将一个圆外的点加入圆中,由于将所有点的顺序都随机了一遍,所以效率成了期望$O(n)$?…真的吗…

可以证明每次添加的点都在圆周上 据说证明好复杂…反正是可以证的…

然后挑圆内的点逐渐扩大半径直至覆盖新加的点与原来的点(通过两条弦的垂线的焦点来确定圆心,公式请自行手推)

这样半径就会一直递增,直到覆盖所有点

程序中计算三点的外接圆的方式是:算出两点连线的中垂线的解析式,然后求两个中垂线的交点(似乎不会出现除0错误)

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
61
62
63
64
65
66
67
68
69
program bzoj_3564;
uses math;
const eps=1e-6;
type rec=record x,y:extended; end;
var p:array[1..50000]of rec;
n,i,j,k,d:longint;
px,py,ox,oy,r,pi,a:extended;
procedure swap(var a,b:rec);
var p:rec;
begin
p:=a;
a:=b;
b:=p;
end;
function dis(x1,y1,x2,y2:extended):extended;
begin
exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
end;
procedure calc(a,b,c,d,e,f:extended); //ax+by+c=0 dx+ey+f=0
begin
ox:=(b*f-e*c)/(a*e-d*b);
oy:=(a*f-d*c)/(d*b-a*e);
end;
begin
pi:=arccos(-1);
read(n);
for i:=1 to n do read(p[i].x,p[i].y);
read(d);
a:=(-d/180)*pi;
read(d);
for i:=1 to n do
begin
px:=p[i].x;
py:=p[i].y;
p[i].x:=(px*cos(a)-py*sin(a))/d;
p[i].y:=px*sin(a)+py*cos(a);
end;
randomize;
for i:=n downto 2 do swap(p[i],p[random(i-1)+1]);
ox:=p[1].x;
oy:=p[1].y;
r:=0;
for i:=2 to n do
if dis(p[i].x,p[i].y,ox,oy)>r+eps then
begin
ox:=p[i].x;
oy:=p[i].y;
r:=0;
for j:=1 to i-1 do
if dis(p[j].x,p[j].y,ox,oy)>r+eps then
begin
ox:=(p[i].x+p[j].x)/2;
oy:=(p[i].y+p[j].y)/2;
r:=dis(ox,oy,p[j].x,p[j].y);
for k:=1 to j-1 do
if dis(p[k].x,p[k].y,ox,oy)>r+eps then
begin
calc(p[i].x-p[j].x,p[i].y-p[j].y,(p[j].x-p[i].x)*(p[i].x+p[j].x)/2+(p[j].y-p[i].y)*(p[i].y+p[j].y)/2,
p[k].x-p[i].x,p[k].y-p[i].y,(p[i].x-p[k].x)*(p[k].x+p[i].x)/2+(p[i].y-p[k].y)*(p[k].y+p[i].y)/2);
r:=dis(ox,oy,p[k].x,p[k].y);
end;
end;
end;
writeln(r:0:3);
end.