문제 소개
2차원 평면상에 놓여 있는 두 개의 축에 평행한 직사각형이 차지하는 전체 면적을 구하는 프로그램을 만들어 보겠습니다. 여기서 각 직사각형은 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표로 정의됩니다.
첫 번째 직사각형은 왼쪽 아래 점 (A, B)와 오른쪽 위 점 (C, D)로 정의되고, 두 번째 직사각형은 왼쪽 아래 점 (E, F)와 오른쪽 위 점 (G, H)로 정의됩니다.
접근 방법
핵심 아이디어는 단순합니다. 두 직사각형의 넓이를 각각 계산하여 더한 뒤, 두 직사각형이 겹치는 부분이 있다면 그 겹친 영역의 넓이를 한 번 빼주면 됩니다. 겹치는 부분을 빼지 않으면 중복된 영역이 두 번 계산되기 때문입니다.
구체적인 해결 단계는 다음과 같습니다.
- width_1 := |C−A|, height_1 := |D−B| — 첫 번째 직사각형의 가로·세로 길이
- width_2 := |G−E|, height_2 := |H−F| — 두 번째 직사각형의 가로·세로 길이
- area := width_1 × height_1 + width_2 × height_2 — 두 넓이의 합
- 겹침 여부 확인: (G < A) 또는 (E > C) 또는 (F > D) 또는 (H < B)라면
- area를 그대로 반환
- 그렇지 않다면(겹치는 경우)
- p := max(A, E), q := max(B, F) — 겹친 영역의 왼쪽 아래 꼭짓점
- r := min(C, G), s := min(D, H) — 겹친 영역의 오른쪽 위 꼭짓점
- width_3 := |r−p|, height_3 := |s−q| — 겹친 영역의 가로·세로 길이
- area − (width_3 × height_3) 반환
겹침 조건을 자세히 살펴보면, G < A는 두 번째 직사각형이 첫 번째보다 완전히 왼쪽에 있다는 뜻이고, E > C는 완전히 오른쪽에, F > D는 완전히 위에, H < B는 완전히 아래에 있다는 의미입니다. 이 네 조건 중 하나라도 참이면 두 직사각형은 서로 닿지 않으므로 겹친 영역이 존재하지 않습니다.
예제 코드
아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
def solve(A, B, C, D, E, F, G, H):
width_1 = abs(C-A)
height_1 = abs(D-B)
width_2 = abs(G-E)
height_2 = abs(H-F)
area = width_1*height_1 + width_2*height_2
if (G<A) or (E>C) or (F>D) or (H<B):
return area
else:
p = max(A,E)
q = max(B,F)
r = min(C,G)
s = min(D,H)
width_3 = abs(r-p)
height_3 = abs(s-q)
return area - (width_3*height_3)
A = -3
B = 0
C = 3
D = 4
E = 0
F = -1
G = 9
H = 2
print(solve(A, B, C, D, E, F, G, H))
입력
-3, 0, 3, 4, 0, -1, 9, 2
출력
45
동작 과정 분석
위 예제에서 첫 번째 직사각형은 (-3, 0)부터 (3, 4)까지, 두 번째 직사각형은 (0, -1)부터 (9, 2)까지의 범위를 가집니다. 첫 번째 직사각형의 넓이는 6 × 4 = 24, 두 번째 직사각형의 넓이는 9 × 3 = 27이므로 두 넓이의 합은 51입니다.
두 직사각형은 (0, 0)부터 (3, 2)까지의 영역에서 서로 겹치며, 이 겹친 부분의 넓이는 3 × 2 = 6입니다. 따라서 최종 결과는 51 − 6 = 45가 됩니다.