overlapped_rectangle_perimeter.md

def calculate_perimeter(rectangles):
    x_coords = set()
    y_coords = set()
    for rect in rectangles:
        x1, y1, x2, y2 = rect
        x_coords.add(x1)
        x_coords.add(x2)
        y_coords.add(y1)
        y_coords.add(y2)

    x_coords = sorted(list(x_coords))
    y_coords = sorted(list(y_coords))

    # create a grid of 0's
    grid = []
    for i in range(len(y_coords)):
        row = []
        for j in range(len(x_coords)):
            row.append(0)
        grid.append(row)

    # mark the interior points with 1's
    for rect in rectangles:
        x1, y1, x2, y2 = rect
        x1_idx = x_coords.index(x1)
        x2_idx = x_coords.index(x2)
        y1_idx = y_coords.index(y1)
        y2_idx = y_coords.index(y2)
        for i in range(y1_idx, y2_idx):
            for j in range(x1_idx, x2_idx):
                grid[i][j] = 1

    # calculate the perimeter of the boundary
    perimeter = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                if i == 0 or grid[i-1][j] == 0:
                    perimeter += y_coords[i+1] - y_coords[i]
                if i == len(grid)-1 or grid[i+1][j] == 0:
                    perimeter += y_coords[i+1] - y_coords[i]
                if j == 0 or grid[i][j-1] == 0:
                    perimeter += x_coords[j+1] - x_coords[j]
                if j == len(grid[0])-1 or grid[i][j+1] == 0:
                    perimeter += x_coords[j+1] - x_coords[j]

    return perimeter

# read input data from file
with open('input.txt', 'r') as f:
    rectangles = []
    for line in f:
        coords = line.strip().split()
        rectangles.append(tuple(map(int, coords)))

# calculate perimeter
perimeter = calculate_perimeter(rectangles)

print(perimeter)