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错误）

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.