数据太大了吗?全爆0

P1429 平面最近点对(加强版)

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] 那要怎么解决。。。


|