我有一段代码，使用旋转卡壳算法，定义了两个距离最远的点。
该代码在第一行输入点的数量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]))
