清帝之惑之雍正

var

n:longint;

x,y:array[1..100000]of int64;

function min(a,b:longint):longint;

begin

min:=a;

if b<a then min:=b;

end;

function dis(i,j:longint):extended;

var

x1,y1,x2,y2:int64;

begin

x1:=x[i];y1:=y[i];

x2:=x[j];y2:=y[j];

dis:=sqrt(sqr(x1-x2)+sqr(y1-y2));

end;

procedure Qsort1(l,r: longint);

var

i,j,x1,y1,t: longint;

begin

i:=l; j:=r;

x1:=x[(l+r) div 2];

repeat

while x[i]<x1 do inc(i);

while x1<x[j] do dec(j);

if not(i>j) then

begin

t:=x[i];x[i]:=x[j];x[j]:=t;

t:=y[i];y[i]:=y[j];y[j]:=t;

inc(i);dec(j);

end;

until i>j;

if l<j then Qsort1(l,j);

if i<r then Qsort1(i,r);

end;

procedure Qsort2(l,r: longint);

var

i,j,x1,y1,t: longint;

begin

i:=l; j:=r;

y1:=y[(l+r) div 2];

repeat

while y[i]<y1 do inc(i);

while y1<y[j] do dec(j);

if not(i>j) then

begin

t:=x[i];x[i]:=x[j];x[j]:=t;

t:=y[i];y[i]:=y[j];y[j]:=t;

inc(i);dec(j);

end;

until i>j;

if l<j then Qsort2(l,j);

if i<r then Qsort2(i,r);

end;

procedure init;

var

i,j,k:longint;

ans,tot:extended;

begin

read(n);

for i:=1 to n do

read(x[i],y[i]);

Qsort1(1,n);

ans:=maxlongint;

for i:=1 to n-1 do

for j:=i+1 to n do

if x[j]-x[i]<ans then

begin

tot:=dis(i,j);

if tot<ans then ans:=tot;

end else break;

Qsort2(1,n);

for i:=1 to n-1 do

for j:=i+1 to n do

if y[j]-y[i]<ans then

begin

tot:=dis(i,j);

if tot<ans then ans:=tot;

end else break;

writeln(ans:0:3);

end;

begin

init;

end.

0 条评论

目前还没有评论...

信息

ID
1012
难度
7
分类
计算几何 点击显示
标签
递交数
4133
已通过
879
通过率
21%
被复制
18
上传者