Rotating Calipers Diameter

Problem

Return the squared diameter of a set of points: the maximum squared distance between any two of them, found from the convex hull of the set.

Build the hull with monotone chain, then for each hull edge advance the farthest antipodal vertex while the triangle area increases, testing the distances to both edge endpoints. Return 0 for fewer than two distinct points.

Hint

The diameter of a point set is always achieved by two hull vertices.

Test cases

case 1

in: [[[0,0],[1,0],[1,1],[0,1]]]

expected: 2

case 2

in: [[[0,0],[3,0],[0,4]]]

expected: 25

case 3

in: [[[0,0],[1,1],[2,2]]]

expected: 8

case 4

in: [[[5,5]]]

expected: 0

case 5

in: [[[0,0],[2,0],[1,3]]]

expected: 10

Starter codePython

def rotating_calipers_diameter(points):
    # Your code here
    pass

5 test cases · run your code against them in the editor