[구현/수학] 백준 2669 직사각형 네개의 합집합의 면적 구하기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2669번: 직사각형 네개의 합집합의 면적 구하기

 

 

 

2. 문제 풀이

 직사각형 네개의 합집합의 면적을 구하는 문제입니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 

 단순히 입력된 4개의 직사각형 넓이를 구하는 건 쉽지만, 겹쳐진 부분의 넓이를 구하긴 어렵습니다. 따라서 직사각형의 영역을 1*1 정사각형으로 좌표화해서 표시했습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
board = [[0]*101 for _ in range(101)]
for _ in range(4):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(x1, x2):
        for j in range(y1, y2):
            board[i][j] = 1

# 출력
res = 0
for i in board:
    res += sum(i)
print(res)

 겹쳐진 부분을 일일이 계산하기가 힘들기 때문에, 아예 100 * 100 보드판을 만들어서 직사각형의 영역을 표시했습니다. 위와 같이 표시하면, 직사각형이 겹쳐져도 중복해서 넓이를 계산하지 않습니다.