[백준] 2669번 직사각형 네 개의 합집합의 면적 구하기 [Python] - 도형

 

 

주어진 직사각형들이 차지하는 총 넓이 구하는 문제$($겹치는 구간 처리$)$

문제

평면에 네 개의 직사각형이 놓여 있는데 그 밑변은 모두 가로축에 평행하다. 이 네 개의 직사각형들은 서로 떨어져 있을 수도 있고, 겹쳐 있을 수도 있고, 하나가 다른 하나를 포함할 수도 있으며, 변이나 꼭짓점이 겹칠 수도 있다.

이 직사각형들이 차지하는 면적을 구하는 프로그램을 작성하시오.

2669번: 직사각형 네개의 합집합의 면적 구하기 (acmicpc.net)

 

100x100 크기의 판에 주어진 좌표 정보에 따라 직사각형이 차지하는 공간을 1로 아닌 공간을 0으로 채웠습니다.

한 직사각형의 가로가 x1 부터 x2 까지의 점을 가지고 있을 때 가로의 길이는 x2 - x1 - 1이라서

x1부터 x2-1까지를 그 직사각형의 가로가 차지하는 넓이로 생각해서 풀었습니다.

board = [[0]*100 for _ in range(100)]

for _ in range(4):
     x1, y1, x2, y2 = map(int, input().split())
     for row in range(y1, y2):
          board[row][x1:x2] = [1]*(x2-x1)

total = 0
for b in board:
     total += sum(b)

print(total)

 

보드 판을 채우지 않고 set을 이용해 중복을 제외해서 각 $($x,y$)$ 점을 구해서 set의 원소의 개수를 출력하는 방법입니다.

s = set()
for _ in range(4):
    x1, y1, x2, y2 = map(int, input().split())
    s.update({(col,row) for col in range(x1, x2) for row in range(y1, y2)})
print(len(s))

 

예제 입력 1

1 2 4 4
2 3 5 7
3 1 6 5
7 3 8 6

예제 출력 1

26