문제
2차원 평면에 점들이 주어집니다. 주어진 모든 점들은 하나 이상의 직사각형으로 덮어져야 합니다. 또한 같은 조건을 만족해야 합니다.
- 직사각형의 모든 변들은 좌표축과 평행합니다.
- 직사각형의 중앙은 원점(0,0)입니다.
- 점을 덮는다는 것은 그 점이 직사각형 안에 있거나 경계선 위에 있다는 것입니다.
물론, 큰 직사각형 하나로도 모든 점들을 덮을 수는 있지만 면적이 넓습니다.
모든 점들을 하나 또는 여러 직사각형으로 덮을 때 직사각형 면적 합의 최소를 구하는 프로그램을 작성하세요.
입력
첫 번째 줄에 점들의 수 N이 주어집니다. (1 ≤ N ≤ 5,000)
그 다음 각 줄마다 N개의 점들의 좌표 X, Y가 주어집니다. (-50,000,000 ≤ X, Y ≤ 50,000,000 , XY ≠ 0)
출력
모든 점을 덮을 수 있는 직사각형 면적들의 합의 최소를 출력합니다.
예제 #1
2
1 1
-1 -1
4
예제 #2
3
-7 19
9 -30
25 10
2080
예제 #3
6
1 20
3 17
5 15
8 12
9 11
10 10
760
예제 #4
4
-11 -1
-3 -15
6 13
-10 9
644
예제 #5
3
3 15
6 13
11 9
660
태그
출처
COCI 2017/2018 contest6 4
로그인해야 코드를 작성할 수 있어요.