比赛 |
20120717 |
评测结果 |
PPPPPPPPPP |
题目名称 |
信使问题b |
最终得分 |
50 |
用户昵称 |
wo shi 刘畅 |
运行时间 |
0.506 s |
代码语言 |
Pascal |
内存使用 |
3.25 MiB |
提交时间 |
2012-07-17 22:02:11 |
显示代码纯文本
const
oo=1000000000000;
type
jp=record
x,y:double;
end;
var
n,i:longint;
a,b:array[0..100000]of jp;
function min(x,y:double):double;
begin
if x<y then min:=x
else min:=y;
end;
procedure sort(l,r:longint);
var
i,j:longint;
xx,yy:double;
begin
i:=l;
j:=r;
xx:=a[(l+r) div 2].x;
repeat
while a[i].x<xx do inc(i);
while xx<a[j].x do dec(j);
if i<=j then
begin
yy:=a[i].x;
a[i].x:=a[j].x;
a[j].x:=yy;
yy:=a[i].y;
a[i].y:=a[j].y;
a[j].y:=yy;
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure sortt(l,r:longint);
var
i,j:longint;
xx,yy:double;
begin
i:=l;
j:=r;
xx:=b[(l+r) div 2].y;
repeat
while b[i].y<xx do inc(i);
while xx<b[j].y do dec(j);
if i<=j then
begin
yy:=b[i].x;
b[i].x:=b[j].x;
b[j].x:=yy;
yy:=b[i].y;
b[i].y:=b[j].y;
b[j].y:=yy;
inc(i);
dec(j);
end;
until i>j;
if i<r then sortt(i,r);
if l<j then sortt(l,j);
end;
function dis(i,j:longint):double;
var
x1,y1,x2,y2:double;
begin
x1:=a[i].x;
y1:=a[i].y;
x2:=a[j].x;
y2:=a[j].y;
dis:=sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
end;
function diss(i,j:longint):double;
var
x1,y1,x2,y2:double;
begin
x1:=b[i].x;
y1:=b[i].y;
x2:=b[j].x;
y2:=b[j].y;
diss:=sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
end;
function closest(l,r:longint):double;
var
mid,i,j,t:longint;
d1,d2,d:double;
begin
if l=r then exit(oo);
if l+1=r then exit(dis(l,r));
mid:=(l+r) div 2;
d1:=closest(l,mid);
d2:=closest(mid+1,r);
d:=min(d1,d2);
t:=0;
for i:=l to r do
if ((a[mid].x-a[i].x<=d)and(i<=mid))
or((a[i].x-a[mid].x<=d)and(i>mid))then
begin
inc(t);
b[t].x:=a[i].x;
b[t].y:=a[i].y;
end;
sortt(1,t);
for i:=1 to t do
for j:=i+1 to t do
begin
if b[j].y-b[i].y>d then break;
d:=min(d,diss(i,j));
end;
closest:=d;
end;
begin
assign(input,'postmanb.in'); reset(input);
assign(output,'postmanb.out'); rewrite(output);
readln(n);
for i:=1 to n do readln(a[i].x,a[i].y);
sort(1,n);
writeln(0.0000);
writeln(closest(1,n):0:4);
close(input);
close(output);
end.