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)
Created
March 26, 2023 05:44
-
-
Save sxhmilyoyo/2baeac8757e4b16cb95388a991475677 to your computer and use it in GitHub Desktop.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment