볼록한 선체에서 점 사이의 최대 거리

Question

평면 (2D)에서 두 점 사이의 최대 거리를 찾아야하는 문제를 해결하고 있습니다. 따라서 계산하는 O (n^2) 방법이 있습니다. 그래프의 모든 점 사이의 거리. 또한 볼록 선체 알고리즘을 구현했습니다. 이제는 O (nlogn)에서 convex hull을 계산 한 다음 O (n^2) 알고리즘을 사용하여 convex hull에서 점 사이의 최대 거리를 계산합니다.

O (N^2)

def d(l1,l2): 
    return ((l2[0]-l1[0])**2+(l2[1]-l1[1])**2) 
def find_max_dist(L): 
    max_dist = d(L[0], L[1]) 
    for i in range(0, len(L)-1): 
     for j in range(i+1, len(L)): 
      max_dist = max(d(L[i], L[j]), max_dist) 
    return max_dist 

볼록 선체

: 볼록 선체의 최대 거리를 계산하기 위해이보다 나은 방법이 여기

내 알고리즘되어 있는가

def convex_hull(points): 
    """Computes the convex hull of a set of 2D points. 

     Input: an iterable sequence of (x, y) pairs representing the points. 
     Output: a list of vertices of the convex hull in counter-clockwise order, 
     starting from the vertex with the lexicographically smallest coordinates. 
     Implements Andrew's monotone chain algorithm. O(n log n) complexity. 
""" 

     # Sort the points lexicographically (tuples are compared lexicographically). 
     # Remove duplicates to detect the case we have just one unique point. 
     points = sorted(set(points)) 

     # Boring case: no points or a single point, possibly repeated multiple times. 
    if len(points) <= 1: 
     return points 

    # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product. 
    # Returns a positive value, if OAB makes a counter-clockwise turn, 
    # negative for clockwise turn, and zero if the points are collinear. 
    def cross(o, a, b): 
     return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) 

    # Build lower hull 
    lower = [] 
    for p in points: 
     while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: 
      lower.pop() 
     lower.append(p) 

    # Build upper hull 
    upper = [] 
    for p in reversed(points): 
     while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: 
      upper.pop() 
     upper.append(p) 

    # Concatenation of the lower and upper hulls gives the convex hull. 
    # Last point of each list is omitted because it is repeated at the beginning of the other list. 
    return lower[:-1] + upper[:-1] 

(210)

전체 알고리즘 지금은 내 방식의 실행 시간을 개선하고이를 계산하는 더 나은 방법이 어떻게

l=[] 
for i in xrange(int(raw_input())): # takes input denoting number of points in the plane 
    n=tuple(int(i) for i in raw_input().split()) #takes each point and makes a tuple 
    l.append(n)        # appends to n 

if len(l)>=10: 
     print find_max_dist(convex_hull(l)) 
else: 
     print find_max_dist(l) 

?

Answer 1

일단 볼록 선체가 있으면 선형 시간으로 두 개의 가장 먼 지점을 찾을 수 있습니다.

두 개의 포인터를 유지하는 것이 좋습니다. 하나는 현재 가장자리를 가리키고 (항상 하나씩 증가) 다른 하나는 꼭지점을 가리 킵니다.

답변은 가장자리의 끝점과 모든 가장자리의 꼭지점 사이의 최대 거리입니다.

(증명은 짧지도 사소하지도 않으므로 여기에 게시하지 않습니다.) 첫 번째 포인터를 이동 한 후에 매번 두 번째 포인터를 늘리면 선과 꼭지점을 통과하는 선을 사용하면 최적의 답을 찾을 수 있습니다.