数组两点之间的最长路径

Question

我有一个代码，使用旋转卡尺的算法，定义两个距离最长的点。

代码在第一行中取点N的个数，然后N次取点X，Y的坐标，在显示最长距离的长度之后。

例如：

INPUT
6
1 1
-1 0
-3 -1
-2 -2
2 3
4 -2

OUTPUT
7.0710678119

INPUT
6
2 2
0 -3
5 7
3 3
2 1
-1 1

OUTPUT
4.47213595499958 #my comment: from (3,3) to (5,7)

但在某些情况下，3或更多的点位于一条直线上。那我该怎么办？

from math import *

def rast(x1, x2, y1, y2):
        x = x2-x1
        y = y2-y1
        l = sqrt(pow(fabs(x), 2)+pow(fabs(y), 2));
        return l

def orientation(p,q,r):
    '''Return positive if p-q-r are clockwise, neg if ccw, zero if colinear.'''
    return (q[1]-p[1])*(r[0]-p[0]) - (q[0]-p[0])*(r[1]-p[1])

def hulls(Points):
    '''Graham scan to find upper and lower convex hulls of a set of 2d points.'''
    U = []
    L = []
    Points.sort()
    for p in Points:
        while len(U) > 1 and orientation(U[-2],U[-1],p) <= 0: U.pop()
        while len(L) > 1 and orientation(L[-2],L[-1],p) >= 0: L.pop()
        U.append(p)
        L.append(p)
    return U,L

def rotatingCalipers(Points):
    '''Given a list of 2d points, finds all ways of sandwiching the points
between two parallel lines that touch one point each, and yields the sequence
of pairs of points touched by each pair of lines.'''
    U,L = hulls(Points)
    i = 0
    j = len(L) - 1
    while i < len(U) - 1 or j > 0:
        yield U[i],L[j]

        # if all the way through one side of hull, advance the other side
        if i == len(U) - 1: j -= 1
        elif j == 0: i += 1

        # still points left on both lists, compare slopes of next hull edges
        # being careful to avoid divide-by-zero in slope calculation
        elif (U[i+1][1]-U[i][1])*(L[j][0]-L[j-1][0]) > \
                (L[j][1]-L[j-1][1])*(U[i+1][0]-U[i][0]):
            i += 1
        else: j -= 1

def diameter(Points):
    '''Given a list of 2d points, returns the pair that's farthest apart.'''
    diam,pair = max([((p[0]-q[0])**2 + (p[1]-q[1])**2, (p,q))
                     for p,q in rotatingCalipers(Points)])
    return pair

n=int(input())
dots = []
for i in range(n):
    tmp = [int(j) for j in input().split()]
    dots.append([tmp[0],tmp[1]])
tmp = diameter(dots)
d1,d2=tmp[0],tmp[1]
print(rast(d1[0],d2[0],d1[1],d2[1]))

Answer 1

一旦你做了凸壳，你将需要排序的线条最长。在我的例子中，您将有红线，在此之后是蓝色的箭头。

​

​

取最长的线(红色)并得到它的角度。凸壳中的前缘点，检查S和P之间的线是否等于角度。如果是这样的话，计算两行SP & EP的距离，如果一条长于蓝线，那是最长的一条线，你可以停下来。否则，忽略红线，并采取下一个最长。当没有相等的角度时，你可以停下来。