최소 넓이 외접 직사각형
다이아몬드 III의견: 0
평면 위에 \(N\)개의 점이 주어진다. 이 모든 점을 내부 또는 경계에 포함하는 직사각형 중 넓이가 가장 작은 것을 찾고자 한다. 직사각형은 좌표축에 평행할 필요가 없으며 임의의 방향으로 회전할 수 있다.
이러한 최소 넓이 외접 직사각형의 넓이를 구하여라.
\(1 \le N \le 100{,}000\)
\(-10^6 \le x_i, y_i \le 10^6\)
첫 줄에 점의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각 점의 좌표 \(x_i\), \(y_i\)가 주어진다. 점의 좌표는 정수이다.
모든 점을 포함하는 최소 넓이 직사각형의 넓이를 출력한다. 절대 오차 또는 상대 오차가 \(10^{-4}\) 이하이면 정답으로 인정된다. 모든 점이 한 직선 위에 있거나 점이 두 개 이하인 경우 넓이는 \(0\)이다.
5
0 0
4 0
4 3
0 3
2 1
12.000000점들이 가로 \(4\), 세로 \(3\) 직사각형 안에 들어 있고 그 방향이 최적이므로 최소 외접 직사각형의 넓이는 \(4 \times 3 = 12\)이다.
4
0 1
1 0
2 1
1 2
2.000000네 점은 한 변의 길이가 \(\sqrt2\)인 기울어진 정사각형을 이룬다. 변에 맞춘 직사각형의 넓이는 \(\sqrt2 \times \sqrt2 = 2\)로, 축에 평행한 외접 사각형 넓이 \(4\)보다 작다. 답은 \(2\)이다.
riseoj 작성
출처 Original
평가 및 의견
최소 넓이 외접 직사각형
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최소 넓이 외접 직사각형