Cover
레이팅 미적용의견: 0
1 \(s / 64\) \(MB / 120\) points
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:
●
The sides of each rectangle are parallel with the coordinate axes,
●
The center of each rectangle is in the origin, i.e. point (0, 0),
●
Each given point is located either inside of the rectangle or on its boundaries.
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.
In test cases worth 40% of total points, it will hold \(N\) ≤ 20.
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 \le 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
3
-7 19
9 -30
25 10
6
1 20
3 17
5 15
8 12
9 11
10 10output
output
4
2080
760Clarification 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
1 s / 64 MB / 120 points
covers the first two points. If we wanted to cover all the points using one rectangle, it would be of
dimensions 50 x 60.
평가 및 의견
Cover
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cover