jarvis_march.coco

data point(x=0, y=0):
    def __str__(self):
        return f'({self.x}, {self.y})'

# Is the turn counter-clockwise?
def counter_clockwise(point(p1), point(p2), point(p3)) =
    (p3.y - p1.y) * (p2.x - p1.x) >= (p2.y - p1.y) * (p3.x - p1.x)


def jarvis_march(gift: point[]) -> point[]:
    point_on_hull = min(gift) # The leftmost point in the gift
    hull = [point_on_hull] # It is guaranteed it will be on the hull.

    while True:
        # Candidate for the next point in the hull
        endpoint = gift[0]
        for p in gift:
            if (endpoint == point_on_hull
                or not counter_clockwise(p, hull[-1], endpoint)):
                endpoint = p

        point_on_hull = endpoint

        # Check if the gift is completely covered.
        if hull[0] == endpoint:
            return hull
        hull.append(point_on_hull)


if __name__ == '__main__':
    test_gift = [
        (-5, 2), (5, 7), (-6, -12), (-14, -14), (9, 9),
        (-1, -1), (-10, 11), (-6, 15), (-6, -8), (15, -9),
        (7, -7), (-2, -9), (6, -5), (0, 14), (2, 8)
    ] |> map$(t -> point(*t)) |> list
    hull = jarvis_march(test_gift)

    print("[#] The points in the hull are:")
    for point in hull:
        print(point)