A simple polygon (edges don't cross) is given by its corners in order, as (x, y) integer tuples; the last corner connects back to the first.
Write doubled_signed_area(poly: list[tuple[int, int]]) -> int returning twice the polygon's signed area:
- positive when the corners go counter-clockwise, negative when they go clockwise;
- its absolute value is twice the area, which is always an integer for integer corners, so you never need floats.
The shoelace formula sums the cross product of each consecutive pair of corners, wrapping around at the end:
2 · area = Σ (x_i · y_{i+1} − x_{i+1} · y_i) with index i+1 taken mod n
doubled_signed_area([(0, 0), (4, 0), (4, 3), (0, 3)]) # 24 (4x3 rectangle, counter-clockwise)
doubled_signed_area([(0, 0), (0, 3), (4, 3), (4, 0)]) # -24 (same rectangle, clockwise)
doubled_signed_area([(0, 0), (1, 0), (0, 1)]) # 1 (triangle of area 1/2)
For fewer than 3 corners, or if all corners are collinear, the answer is 0.
Constraints: 0 <= len(poly) <= 10^5, coordinates between -10^9 and 10^9.
Show hint
Loop over zip(poly, poly[1:] + poly[:1]) and add x1 * y2 - x2 * y1 for each edge; don't forget the closing edge from the last corner back to the first.