문제 소개
2차원 평면 위에 놓인 두 개의 직사각형(변이 축에 평행한 사각형)이 덮고 있는 총 면적을 구하는 문제입니다. 각 직사각형은 아래 그림과 같이 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표로 정의됩니다.
첫 번째 직사각형은 (A, B)~(C, D), 두 번째 직사각형은 (E, F)~(G, H)로 표현합니다. 주의할 점은 두 사각형이 겹치는 영역이 있을 경우 그 부분을 한 번만 계산해야 한다는 것입니다.
해결 접근 방법
이 문제의 핵심은 다음과 같습니다.
- 두 사각형이 겹치지 않는다면 두 면적을 단순히 더하면 됩니다.
- 겹친다면 두 면적의 합에서 겹치는 영역의 면적을 빼주어야 중복 계산을 막을 수 있습니다.
알고리즘을 단계별로 정리하면 다음과 같습니다.
- 두 사각형이 겹치지 않는 경우, 즉 C ≤ E 또는 A ≥ G 또는 B ≥ H 또는 D ≤ F라면 (C−A)×(D−B) + (G−E)×(H−F)를 바로 반환합니다.
- x좌표인 A, C, E, G를 배열 h에 저장합니다.
- y좌표인 B, D, F, H를 배열 v에 저장합니다.
- 두 배열을 각각 오름차순으로 정렬합니다.
- 정렬 후 가운데 두 원소의 차가 곧 겹치는 구간의 길이이므로, 겹치는 면적은 temp = (h[2]−h[1]) × (v[2]−v[1])로 구할 수 있습니다.
- 최종 답은 total = (C−A)×(D−B) + (G−E)×(H−F) − temp 입니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
if(C <= E || A >= G || B >= H || D <= F) return (C - A) * (D - B) + (G - E) * (H - F);
vector<int> h;
h.push_back(A);
h.push_back(C);
h.push_back(E);
h.push_back(G);
vector<int> v;
v.push_back(B);
v.push_back(D);
v.push_back(F);
v.push_back(H);
sort(h.begin(), h.end());
sort(v.begin(), v.end());
long long int temp = (h[2] - h[1]) * (v[2] - v[1]);
long long int total = -temp;
total += (C - A) * (D - B);
total += (G - E) * (H - F);
return total;
}
};
main(){
Solution ob;
cout << (ob.computeArea(-3, 0, 3, 4, 0, -1, 9, 2));
}
입력
-3 0 3 4 0 -1 9 2
출력
45
예제 동작 분석
입력값 (-3, 0, 3, 4)과 (0, -1, 9, 2)를 기준으로 계산 과정을 살펴보겠습니다.
- 첫 번째 직사각형: 너비 3−(−3)=6, 높이 4−0=4 → 면적 24
- 두 번째 직사각형: 너비 9−0=9, 높이 2−(−1)=3 → 면적 27
- 겹치는 영역: x구간 [0, 3], y구간 [0, 2] → 면적 3×2=6
- 총 면적: 24 + 27 − 6 = 45
따라서 프로그램 실행 시 최종 결과로 45가 출력되는 것을 확인할 수 있습니다.