pascal编程的一道题：最近点对距离问题

来源：百度知道 编辑：UC知道 时间：2024/06/06 11:30:42
给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。严格的说，最近点对可能多于一对。为了简单起见，这里只找一对。
输入：平面内各点的坐标，以（0，0）表示输入结束（每行一个点的坐标）输出：距离最近的两点坐标。
分析：由于直接分析法太耗时，所以将问题缩小化，将一个大问题缩小为两个小问题，其中一个问题的大小为n/2；这样出现最近点对的情况有以下三种：
情况1：两个点都出现在A中；
情况2：两个点都出现在B中；
情况3：一个点在A中，一个点在B中；
分别找出这三种情况下距离最近的点对，而最近的点对必定是这三种情况下距离值最小的。
有人知道这个程序怎么编阿，尤其是对于第三种情况的处理，知道的告诉下，本人非常感谢！！！！！！！！！！

var
x,y:array[1..60000] of extended;
i,j,k,m,n:longint;
ad:extended;
procedure init;
var i:longint;
begin
readln(n);
for i:=1 to n do readln(x[i],y[i]);
end;
procedure qsort(s,t:longint);
var temp,mdx,mdy:extended;
i,j:longint;
begin
i:=s;j:=t;mdx:=x[(s+t) div 2];mdy:=y[(s+t) div 2];
while i<=j do
begin
while (x[i]<mdx)or(x[i]=mdx)and(y[i]<mdy) do inc(i);
while (x[j]>mdx)or(x[j]=mdx)and(y[j]>mdy) do dec(j);
if i<=j then
begin
temp:=x[i];x[i]:=x[j];x[j]:=temp;
temp:=y[i];y[i]:=y[j];y[j]:=temp;
inc(i);dec(j);
end;
end;
if i<t then qsort(i,t);
if j>s then qsort(s,j);
end;
function min(x,y:extended):extended;
begin
if x>y then exit(y);
exit(x);
end;
function dis(s,t:longint):extended;
begin
exit(sqrt(sqr(x[t]-x[s])+sqr(y[t]-y[s])));