문제
N개의 점이 주어질 때, 모든 점을 포함하는 최소 축 정렬 직사각형의 넓이를 구하라.
입력
첫째 줄에 N, 이후 N줄에 x, y 좌표가 주어진다.
출력
모든 점을 포함하는 최소 직사각형의 넓이를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 1 1 1 -1 -1 1 -1 -1 | 4 |
풀이
x, y 좌표 각각의 최솟값/최댓값을 구하여 가로 * 세로를 계산한다.
- x좌표와 y좌표를 각각 배열에 저장한다
- 배열을 정렬하여 최솟값과 최댓값을 구한다
- (x최대 - x최소) * (y최대 - y최소)가 넓이이다
핵심 아이디어: 축 정렬 바운딩 박스의 넓이는 각 축의 범위(최대 - 최소)의 곱이다.
코드
package day749;
import java.io.*;
import java.util.*;
public class Day729BOJ9063대지 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] A = new int[N];
int[] B = new int[N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
A[i] = Integer.parseInt(st.nextToken());
B[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(A);
Arrays.sort(B);
System.out.println((A[N - 1] - A[0]) * (B[N - 1] - B[0]));
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)