算法训练营 -- 最近点对

描述

给定n个二维平面上的点，求距离最近的一对点，输出他们的距离。

输入

第一行包含一个正整数n。

接下来n行，每行包含两个整数x,y，表示一个点的坐标。

输出

输出距离最近的一对点的距离，保留两位小数。

样例输入

    10
    7 9
    -8 -1
    -3 -1
    1 4
    -3 9
    6 -4
    7 5
    6 6
    -6 10
    0 8

样例输出

1.41

样例解释

距离最近的点为7和8，距离为√(7−6)2+(5−6)2=√2≈1.41(7-6)2+(5-6)2=2≈1.41

提示

分治求最近点对。当然也可以用kdtree，虽然应该会超时。

代码实现

法1：暴力求解（OJ上只能得55分，因为超时）

#!/usr/bin/env pypy3
# encoding=UTF-8

from math import sqrt, pow

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def dis2p(a, b):
    d = sqrt(pow((b.x - a.x), 2) + pow((b.y - a.y), 2))
    return d

def getAnswer(points):
    l = len(points)
    dp = list()
    for i in range(l - 1):
        dl = list()
        for j in range(i + 1, l):
            dis = dis2p(points[i], points[j])
            dl.append(dis)
        dl.sort()
        dp.append(dl[0])
    dp.sort()

    return dp[0]

if __name__ == '__main__':
    n = int(input())
    pts = list()
    for i in range(n):
        x, y = map(int, input().split())
        p = Point(x, y)
        pts.append(p)
    a = getAnswer(pts)
    b = float("%.2f"%a)
    print(b)

法2：DiaC

---

References

1. GeeksforGeeks上的相关介绍