帕斯卡語言實現最近點對問題：分治法求解平面上兩點最小距離

問題描述

給定 n (2 ≤ n ≤ 100,000) 個城市座標 (Xi, Yi)，求最短直線距離 L（保留三位小數）。即平面最近點對問題。

演算法：分治法 O(n log n)

1. 預處理：按 X 座標排序 O(n log n)。
2. 遞歸分治：
   • 分割：中線 x = mid 分為左右兩半。
   • 遞歸求左半 dl、右半 dr 的最小距離 d = min(dl, dr)。
   • 合併：收集距中線 d 以內的點，按 Y 座標排序，對每點僅需檢查後續最多 7 點（幾何證明）。
3. 基礎情況：n ≤ 3 直接暴力 O(1)。

帕斯卡實現框架

type
  Point = record
    x, y: Longint;
  end;

var
  p: array[1..100000] of Point;
  tmp: array[1..100000] of Point;

function dist2(i, j: Longint): Longint; { 回傳平方距離 }
function min(a, b: Longint): Longint;

function closest(l, r: Longint): Longint; { 回傳最小距離平方 }
var
  mid, d, i, j, k: Longint;
  strip: array[1..100000] of Point;
begin
  if r - l <= 2 then begin
    d := MaxLongint;
    for i := l to r do
      for j := i+1 to r do
        d := min(d, dist2(i, j));
    { 合併排序 by y }
    exit(d);
  end;
  mid := (l + r) div 2;
  d := min(closest(l, mid), closest(mid+1, r));
  { 收集 strip 區域點，按 y 排序 }
  k := 0;
  for i := l to r do
    if sqr(p[i].x - p[mid].x) < d then begin
      inc(k); strip[k] := p[i];
    end;
  { 對 strip 內每點檢查後 7 點 }
  for i := 1 to k do
    for j := i+1 to min(i+7, k) do
      if sqr(strip[j].y - strip[i].y) < d then
        d := min(d, dist2(strip[i], strip[j]));
  { 合併排序 by y 回 p }
  exit(d);
end;

關鍵優化

• 使用 Longint 儲存平方距離，避免浮點運算，最後 sqrt(d) 格式化輸出。
• 合併排序復用臨時陣列 tmp，避免重複分配記憶體。
• 輸入坐標範圍 1..2^31，平方距離需 Int64（Int64 在 Free Pascal 為 Int64）。

參考資源

• 分治法最近點對詳解
• 帕斯卡實現範例