这题 写了将近半个月……总是在D各种Bug
总的说来-这题最难应该是在精度处理上
1
1
0 0 1
这组数据过了就说明精度处理差不多了……
Program kingdom;
const
maxn=100;
maxm=100;
le=0.000000001;
type
circle=record
x,y,r:double;
end;
var
s:array[1..maxn,1..1000] of circle;
n,i,j,k:longint;
m:array[1..maxn] of longint;
ans:array[1..maxn,1..4] of double;
wanted:array[1..maxn] of double;
b:array[1..maxn] of boolean;
l,r:double;
function arccos(cosa:double):double;
var
sina,tana:double;
begin
if cosa=0 then exit(pi/2);
sina:=sqrt(1-sqr(cosa));
tana:=sina/cosa;
exit(arctan(tana));
end;
function min(a,b:double):double;
begin
if a<b then exit(a) else exit(b);
end;
function max(a,b:double):double;
begin
if a>b then exit(a) else exit(b);
end;
function sector(a,r:double):double;
begin
exit(a*r*r/2);
end;
function triangle(a,r:double):double;
begin
exit(sin(a)*r*r/2);
end;
function inlside(s:circle;l:double):boolean;
begin
if (s.x-s.r>l) or (abs(s.x-s.r-l)<le) then exit(true) else exit(false);
end;
function inrside(s:circle;r:double):boolean;
begin
if (s.x+s.r<r) or (abs(s.x+s.r-r)<le) then exit(true) else exit(false);
end;
function intarea(s:circle;l,r:double):double;
var
i,j:longint;
a,a2,s1,s2,s3,s4:double;
bl,br:boolean;
begin
if (r<s.x-s.r) or (s.x+s.r<l) then exit(0);
if (s.x<=l) then
begin
a:=arccos((l-s.x)/s.r)*2;
if (abs(s.x-l)<le) then s1:=0
else s1:=triangle(a,s.r);
s2:=sector(a,s.r);
if s.x+s.r>r then
begin
a:=arccos((r-s.x)/s.r)*2;
s3:=sector(a,s.r);
s4:=triangle(a,s.r);
s2:=s2-(s3-s4);
end;
exit(s2-s1);
end
else
if (s.x>=r) then
begin
a:=arccos((s.x-r)/s.r)*2;
if (abs(s.x-r)<le) then s1:=0
else s1:=triangle(a,s.r);
s2:=sector(a,s.r);
if s.x-s.r<l then
begin
a:=arccos((s.x-l)/s.r)*2;
s3:=sector(a,s.r);
s4:=triangle(a,s.r);
s2:=s2-(s3-s4);
end;
exit(s2-s1);
end
else
begin
bl:=inlside(s,l);
br:=inrside(s,r);
if bl and br then exit(pi*s.r*s.r);
if bl and not(br) then
begin
a:=arccos((r-s.x)/s.r)*2;
s3:=sector(a,s.r)-triangle(a,s.r);
exit(pi*s.r*s.r-s3);
end;
if not(bl) and br then
begin
a:=arccos((s.x-l)/s.r)*2;
s3:=sector(a,s.r)-triangle(a,s.r);
exit(pi*s.r*s.r-s3);
end;
a:=arccos((s.x-l)/s.r)*2;
a2:=arccos((r-s.x)/s.r)*2;
s1:=sector(2*pi-a-a2,s.r);
s2:=triangle(a,s.r)+triangle(a2,s.r);
exit(s1+s2);
end;
end;
function place(k:longint;l,r:double):boolean;
var
tot:double;
i,j:longint;
begin
tot:=0;
for j:=1 to m[k] do
begin
tot:=tot+intarea(s[k,j],l,r);
end;
// writeln(tot*n,' ',wanted[k]*pi);
if (abs(tot*n-wanted[k]*pi)<le) then exit(true);
if (tot*n<(wanted[k]*pi)) then exit(false) else exit(true);
end;
function bsearch(r1,r2:double):double;
var
m:double;
i,j,k,num:longint;
flag:boolean;
begin
for k:=1 to 60 do
begin
flag:=false;
m:=(r1+r2)/2;
for i:=1 to n do
if not b[i] then
begin
flag:=flag or place(i,l,m);
if flag then
begin
num:=i;
break;
end;
end;
if flag then r2:=m else r1:=m;
end;
b[num]:=true;
ans[num,1]:=l;
ans[num,2]:=r1;
exit(r1);
end;
begin
{ assign(input,'kingdom.in');
reset(input);
} r:=-10000;
l:=10000;
read(n);
fillchar(b,sizeof(b),false);
fillchar(wanted,sizeof(wanted),0);
for i:=1 to n do
begin
read(m[i]);
for j:=1 to m[i] do
begin
read(s[i,j].x,s[i,j].y,s[i,j].r);
// writeln(s[i,j].x,s[i,j].y,s[i,j].r);
r:=max(r,s[i,j].x+s[i,j].r);
l:=min(l,s[i,j].x-s[i,j].r);
wanted[i]:=wanted[i]+sqr(s[i,j].r);
end;
end;
r:=r+1;
for i:=1 to n do
l:=bsearch(l,r);
for i:=1 to n do
begin
writeln('4');
writeln(ans[i,1]:7:7,' 3000');
writeln(ans[i,1]:7:7,' -3000');
writeln(ans[i,2]:7:7,' -3000');
writeln(ans[i,2]:7:7,' 3000');
end;
// close(input);
end.
