用最少量的矩形填充多边形

import math

def polygon_area(vertices):
    n = len(vertices)
    area = 0.0
    for i in range(n):
        j = (i + 1) % n
        area += vertices[i][0] * vertices[j][1] - vertices[j][0] * vertices[i][1]
    return abs(area) / 2.0

def triangle_area(a, b, c):
    ab = math.dist(a, b)
    bc = math.dist(b, c)
    ca = math.dist(c, a)
    s = (ab + bc + ca) / 2.0
    return math.sqrt(s * (s - ab) * (s - bc) * (s - ca))

def polygon_to_rectangles(vertices):
    n = len(vertices)
    rectangles = []
    for i in range(n):
        j = (i + 1) % n
        if j == n - 1:
            rectangles.append((vertices[i], vertices[j], (0, 0)))
        else:
            k = (j + 1) % n
            area1 = triangle_area(vertices[i], vertices[j], (0, 0))
            area2 = triangle_area(vertices[i], vertices[j], vertices[k])
            if area1 > area2:
                rectangles.append((vertices[i], vertices[j], vertices[k]))
            else:
                rectangles.append((vertices[i], vertices[j], (0, 0)))
    return rectangles

def polygon_to_min_rectangles(vertices):
    rectangles = polygon_to_rectangles(vertices)
    total_area = 0.0
    for r in rectangles:
        area = triangle_area(*r)
        total_area += area
    return total_area