0

给定平面上的点，找到一对两个（不同）点之间的最小距离。回想一下，点 (1, 1) 和 (2, 2) 之间的距离等于 sqrt((x1-x2)**2 + (y1-y2)**2)。

我在 Python 代码（Divide & Conquer）下面写了，但是在一些隐藏的测试用例上给出了错误的答案，我不知道出了什么问题。任何代码更正方面的帮助都将得到衷心的感谢。PS：我已经检查了网络上的其他答案，但是这段代码在哪里做错了？

from math import sqrt
import heapq as hp

def dist(a,b): # 'a' and 'b' are tuples of two points (x1,y1) and (x2,y2)
    (p,q),(x,y)=a,b
    return sqrt((p-x)**2+(q-y)**2)

def solve(a,l,r): #Logic used is of Divide and Conquer
    if r-l<=2:
        if a[l][1]>a[r][1]: #sorting according to 'y' coordinate
            a[l],a[r]=a[r],a[l]
        return dist(a[l],a[r])
    mid=(l+r)//2
    d1=solve(a,l,mid)
    d2=solve(a,mid+1,r)
    d=min(d1,d2)
    z=l
    for i in hp.merge(a[l:mid+1],a[mid+1:r+1],key=lambda x:x[1]):
        a[z]=i
        z+=1
    for i in range(l,r+1):
        if abs(a[i][0]-a[mid][0])<d:
            for j in range(i+1,r+1):
                d=min(d,dist(a[i],a[j]))
    return d

if __name__=='__main__':
    n=int(input()) #number of points 
    l=[]
    for i in range(n): # appending tuples of point in form (x,y)
        l.append(tuple(map(int,input().split())))
    print(solve(l,0,n-1))

# example:
# 4  <- this is n. Below are 'n' points (x,y) 
# 0 0
# 5 6
# 3 4
# 7 2
4

0 回答 0