zls6602488 @ 2015-10-05 15:52:43
全部爆217,215,不知道为什么,数据太大了吗??求大神看下
const inf='.in'; outf='p.out';
type
real=extended;
jss=record
x,y:longint;
end;
var
i,n:longint;
a,tmp:array[0..200001]of jss;
Procedure qsort(l,r:longint);
var i,j:longint; xx,yy:jss;
begin
i:=l; j:=r; xx:=a[(2*l+r)div 3];
repeat
while a[i].x<xx.x do inc(i);
while a[j].x>xx.x do dec(j);
if i<=j then
begin
yy:=a[i]; a[i]:=a[j]; a[j]:=yy;
inc(i); dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
Function dis(dian1,dian2:jss):real;
begin
exit(sqrt(sqr(abs(dian1.x-dian2.x))+sqr(abs(dian1.y-dian2.y))));
end;
Function min1(a,b:real):real;
begin
if a>b then exit(b) else exit(a);
end;
Function min2(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
Procedure sort(l,r:longint);
var i,j:longint; xx,yy:jss;
begin
i:=l; j:=r; xx:=tmp[(2*l+r)div 3];
repeat
while tmp[i].y<xx.y do inc(i);
while tmp[j].y>xx.y do dec(j);
if i<=j then
begin
yy:=tmp[i]; tmp[i]:=a[j]; tmp[j]:=yy;
inc(i); dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
Function find(l,r:longint):real;
var
mid,t1,t2,i,j:longint;
dmin:real;
begin
if l=r then exit(maxlongint);
if l+1=r then exit(dis(a[l],a[r]));
mid:=(l+r)shr 1;
dmin:=min1(find(l,mid),find(mid+1,r));
t1:=mid; t2:=mid+1;
while (t1>=l)and(abs(a[t1].x-a[mid].x)<dmin) do dec(t1);
inc(t1);
while (t2<=r)and(abs(a[t2].x-a[mid].x)<dmin) do inc(t2);
dec(t2);
if (t1=mid+1)or(t2=mid) then exit(dmin);
for i:=t1 to t2 do tmp[i]:=a[i]; //!!!!
sort(t1,t2);
for i:=t1 to t2-1 do
for j:=i+1 to min2(i+8,t2) do
begin
dmin:=min1(dmin,dis(tmp[i],tmp[j]));
end;
exit(dmin);
end;
begin
readln(n);
for i:=1 to n do readln(a[i].x,a[i].y);
qsort(1,n);
writeln(find(1,n):0:4);
end.
by 孙遥 @ 2015-10-05 18:12:19
是的 没错 (⊙v⊙)嗯
by zls6602488 @ 2015-10-05 21:54:45
@[url=/space/show?uid=9993]孙遥[/url] 那要怎么解决。。。