시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 64 MB | 57 | 33 | 32 | 60.377% |
You are given N points in the coordinate system. They need to be covered with one or more rectangles, such that the following conditions are met:
Of course, it is possible to cover all the points using only one rectangle, but this rectangle could have a very large surface area. Our goal is to find a selection of required rectangles such that the sum of their surface areas is minimal.
The first line of input contains the integer N (1 ≤ N ≤ 5000), the number of points.
Each of the following N lines contains two integers X and Y (-50 000 000 ≤ X, Y ≤ 50 000 000, XY ≠ 0), the coordinates of each point.
You must output the required minimal sum of surface areas of the rectangles.
2 1 1 -1 -1
4
3 -7 19 9 -30 25 10
2080
6 1 20 3 17 5 15 8 12 9 11 10 10
760
Clarification of the first test case: We choose the rectangle whose opposite angles are the given points, since it meets the conditions from the task.
Clarification of the second test case: We choose two rectangles with their centers in the origin. The first is of dimensions 50 x 20 and covers point (25, 10). The second is of dimensions 18 x 60 and covers the first two points. If we wanted to cover all the points using one rectangle, it would be of dimensions 50 x 60.