题目就是早从左到右的路
注意输入的实数
这题图画好就行,别像我一开始把图弄反就成
从上开始找,若找到一个与下边界相邻的就无解,找到与左边相邻的记圆与左边界相交的下边的点(相当于左上角挖去一块),右边同理。
Program snake;
const
maxn=1000;
var
n,i,j:longint;
x,y,r,lc,rc:array[1..maxn] of double;
maxl,maxr:double;
father:array[1..maxn] of longint;
b,up,down,left,right:array[1..maxn] of boolean;
function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
Procedure union(x,y:longint);
begin
father[father[x]]:=father[father[y]];
end;
function distance(i,j:longint):double;
begin
exit(sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])));
end;
function dis(x1,y1,x2,y2:double):double;
begin
exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
end;
begin
fillchar(b,sizeof(b),false);
fillchar(up,sizeof(up),false);
fillchar(down,sizeof(down),false);
fillchar(left,sizeof(left),false);
fillchar(right,sizeof(right),false);
fillchar(lc,sizeof(lc),0);
fillchar(rc,sizeof(rc),0);
maxl:=1000;maxr:=1000;
read(n);
for i:=1 to n do
begin
read(x[i],y[i],r[i]);
father[i]:=i;
for j:=1 to i-1 do
if distance(i,j)<r[i]+r[j] then
if getfather(i)<>getfather(j) then
union(i,j);
if (y[i]<r[i]) then down[i]:=true;
if (y[i]+r[i]>1000) then up[i]:=true;
if (x[i]<r[i]) then
begin
left[i]:=true;
lc[i]:=y[i]-sqrt(sqr(r[i])-sqr(x[i]));
end;
if (x[i]+r[i]>1000) then
begin
right[i]:=true;
rc[i]:=y[i]-sqrt(sqr(r[i])-sqr(1000-x[i]));
end;
end;
for i:=1 to n do
if (up[i]) and not(b[i]) then
begin
for j:=1 to n do
if father[i]=father[j] then
begin
b[j]:=true;
if (down[j]) then
begin
writeln('Bill will be bitten.');
halt;
end;
if left[j] then
begin
if lc[j]<maxl then maxl:=lc[j];
end;
if right[j] then
begin
if rc[j]<maxr then maxr:=rc[j];
end;
end;
end;
writeln('Bill enters at (0.00, ',maxl:2:2,') and leaves at (1000.00, ',maxr:2:2,').');
end.