Convex Hull Perimeter

Problem

Given points as [x, y] pairs, return the perimeter of their convex hull as a float, 0.0 for a single point, and twice the segment length for two points.

Build the hull with the monotone chain algorithm, keeping only strict left turns using the cross product, then sum the Euclidean lengths of the hull edges. Duplicate points are removed first.

Hint

A cross product of zero or less means the middle point is not part of the convex hull.

Test cases

case 1

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

expected: 4

case 2

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

expected: 8

case 3

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

expected: 2

case 4

in: [[[5,5]]]

expected: 0

case 5

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

expected: 12

Starter codePython

def convex_hull_perimeter(points):
    # Your code here
    pass

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