문제
두 직사각형의 겹치는 영역의 넓이를 구하라.
입력
두 직사각형의 좌표가 (x1, y1), (x2, y2)와 (x3, y3), (x4, y4)로 주어진다.
출력
겹치는 영역의 넓이를 출력한다. 겹치지 않으면 0을 출력한다.
예제
| 입력 | 출력 |
|---|---|
0 10 10 0 5 15 15 5 | 25 |
풀이
두 직사각형의 교집합 좌표를 구하여 넓이를 계산한다.
- 두 직사각형이 겹치지 않는 조건(분리)을 먼저 확인한다
- 겹치는 경우, 교집합의 좌우/상하 범위를 max/min으로 구한다
- 교집합의 가로 x 세로가 넓이이다
핵심 아이디어: 두 구간의 교집합은 [max(l1, l2), min(r1, r2)]이며, 이를 x축과 y축 각각에 적용하면 겹치는 직사각형을 구할 수 있다.
코드
#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
ll x1, y11, x2, y2, x3, y3, x4, y4;
int main()
{
cin >> x1 >> y11 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
if (x2 < x3 || x1 > x4 || y11 < y4 || y2 > y3)
cout << 0;
else
{
ll lx = max(x1, x3);
ll rx = min(x2, x4);
ll ry = max(y2, y4);
ll ly = min(y11, y3);
cout << abs((rx - lx) * (ry - ly));
}
}복잡도
- 시간: O(1)
- 공간: O(1)