문제
N개의 점이 주어질 때, 모든 점을 포함하는 최소 축 정렬 직사각형의 넓이와 둘레를 구하라.
입력
테스트 케이스 수 T와 각 케이스마다 점의 수 N과 좌표가 주어진다.
출력
각 케이스마다 넓이와 둘레를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 4 0 0 1 0 1 1 0 1 | Case 1: Area 1.000000, Perimeter 4.000000 |
풀이
바운딩 박스를 구하여 넓이와 둘레를 계산한다.
- 모든 점의 x, y 좌표에서 최솟값과 최댓값을 구한다
- 가로 = maxX - minX, 세로 = maxY - minY
- 넓이 = 가로 * 세로, 둘레 = 2 * (가로 + 세로)
핵심 아이디어: 축 정렬 바운딩 박스는 x, y 각각의 min/max로 O(N)에 구할 수 있다.
코드
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int main()
{
int t, n;
cin >> t;
for (int i = 1; i <= t; i++)
{
cin >> n;
double ans, height, width;
double maxX = -INF, maxY = -INF, minX = INF, minY = INF;
for (int i = 0; i < n; i++)
{
double x, y;
cin >> x >> y;
maxX = max(maxX, x);
maxY = max(maxY, y);
minX = min(minX, x);
minY = min(minY, y);
}
height = maxY - minY;
width = maxX - minX;
printf(
"Case %d: Area %f, Perimeter %f\n",
i,
height * width,
height * 2 + width * 2);
}
}복잡도
- 시간: O(N)
- 공간: O(1)