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