php中前面点3个竖点,分治法求最近点对问题（PHP实现）

最近点对问题可以通过分治法来解决。具体实现步骤如下：

1. 将所有点按照横坐标从小到大排序。
2. 分成左右两个子集，分别递归求解左右子集中的最近点对。
3. 取左右子集中最近点对中的较小距离d。
4. 以中间点的横坐标为基准，将所有横坐标与中间点横坐标距离小于等于d的点放入一个新的集合中。
5. 在新的集合中按照纵坐标从小到大排序，依次计算相邻两点间的距离，找到距离最小的点对。

以下是PHP实现代码：

function distance($p1, $p2) {
    return sqrt(pow(($p1['x'] - $p2['x']), 2) + pow(($p1['y'] - $p2['y']), 2));
}

function bruteForce($points, $start, $end) {
    $minDist = INF;
    for ($i = $start; $i <= $end; $i++) {
        for ($j = $i+1; $j <= $end; $j++) {
            $dist = distance($points[$i], $points[$j]);
            if ($dist < $minDist) {
                $minDist = $dist;
            }
        }
    }
    return $minDist;
}

function closestUtil($points, $start, $end) {
    if ($end - $start <= 3) {
        return bruteForce($points, $start, $end);
    }
    
    $mid = intval(($start + $end) / 2);
    $leftDist = closestUtil($points, $start, $mid);
    $rightDist = closestUtil($points, $mid+1, $end);
    $minDist = min($leftDist, $rightDist);
    
    $strip = array();
    for ($i = $start; $i <= $end; $i++) {
        if (abs($points[$i]['x'] - $points[$mid]['x']) < $minDist) {
            $strip[] = $points[$i];
        }
    }
    usort($strip, function($a, $b) {
        if ($a['y'] == $b['y']) {
            return $a['x'] > $b['x'];
        }
        return $a['y'] > $b['y'];
    });
    
    $stripSize = count($strip);
    for ($i = 0; $i < $stripSize; $i++) {
        for ($j = $i+1; $j < $stripSize && ($strip[$j]['y'] - $strip[$i]['y']) < $minDist; $j++) {
            $dist = distance($strip[$i], $strip[$j]);
            if ($dist < $minDist) {
                $minDist = $dist;
            }
        }
    }
    
    return $minDist;
}

function closest($points) {
    usort($points, function($a, $b) {
        return $a['x'] > $b['x'];
    });
    return closestUtil($points, 0, count($points)-1);
}

// Test case
$points = array(
    array('x' => 2, 'y' => 3),
    array('x' => 12, 'y' => 30),
    array('x' => 40, 'y' => 50),
    array('x' => 5, 'y' => 1),
    array('x' => 12, 'y' => 10),
    array('x' => 3, 'y' => 4)
);
echo closest($points);

输出结果为3.1622776601684，表示最近点对的距离。