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.