BZOJ

BZOJ 2823

传送门

嗯复习一下随机增量…

先${\rm shuffle}$一下，然后每次挑一个圆外的点加进来

公示推错QAQ

傻逼extended连四舍五入都不会你吃*去吧 只能用double


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
program bzoj_2823;
const eps=1e-6;
type point=record x,y:double; end;
var p:array[1..1000000]of point;
    n,i,j,k:longint;
    o:point;
    r:double;

procedure swap(var a,b:point);
var p:point;
begin
  p:=a;
  a:=b;
  b:=p;
end;

function dis(a,b:point):double;
begin
  exit(sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)));
end;

procedure calc(a,b,c:point);
var k1,k2,b1,b2:double;
begin
  k1:=(b.x-a.x)/(a.y-b.y);
  k2:=(c.x-b.x)/(b.y-c.y);
  b1:=(a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)/(2*(a.y-b.y));
  b2:=(b.x*b.x-c.x*c.x+b.y*b.y-c.y*c.y)/(2*(b.y-c.y));
  o.x:=(b2-b1)/(k1-k2);
  o.y:=(k2*b1-k1*b2)/(k2-k1);
end;

begin
  randomize;
  readln(n);
  for i:=1 to n do readln(p[i].x,p[i].y);
  for i:=n downto 2 do swap(p[i],p[random(i-1)+1]);
  o:=p[1];
  r:=0;
  for i:=2 to n do if dis(p[i],o)>r+eps then
  begin
    o:=p[i];
    r:=0;
    for j:=1 to i-1 do if dis(o,p[j])>r+eps then
    begin
      o.x:=(p[i].x+p[j].x)/2;
      o.y:=(p[i].y+p[j].y)/2;
      r:=dis(o,p[j]);
      for k:=1 to j-1 do if dis(o,p[k])>r+eps then
      begin
        calc(p[i],p[j],p[k]);
        r:=dis(p[k],o);
      end;
    end;
  end;
  writeln(o.x:0:2,' ',o.y:0:2,' ',r:0:2);
end.