15535번 - Share the Ruins Preservation 다국어

문제

Two organizations International Community for Preservation of Constructions (ICPC) and Japanese Archaeologist Group (JAG) engage in ruins preservation. Recently, many ruins were found in a certain zone. The two organizations decided to share the preservation of the ruins by assigning some of the ruins to ICPC and the other ruins to JAG.

Now, ICPC and JAG make a rule for assignment as follows:

1. Draw a vertical straight line from the north to the south, avoiding to intersect ruins.
2. Ruins located to the west of the line are preserved by ICPC. On the other hand, ruins located to the east of the line are preserved by JAG. (It is possible that no ruins are located to the east/west of the line; in this case, ICPC/JAG will preserve no ruins.)

A problem is where to draw a straight line. For each organization, the way to preserve its assigned ruins is to make exactly one fence such that all the assigned ruins are in the region surrounded by the fence. Furthermore, they should minimize the length of such a fence for their budget. If the surrounded areas are vast, expensive costs will be needed to maintain the inside of areas. Therefore, they want to minimize the total preservation cost, i.e. the sum of the areas surrounded by two fences. Your task is to write a program computing the minimum sum of the areas surrounded by two fences, yielded by drawing an appropriate straight line.

입력

The input consists of a single test case.

N
x1 y1
...
xN yN

The first line contains an integer N (1 ≤ N ≤ 100,000), which is the number of founded ruins. The following N lines represent the location of the ruins. The i-th line of them consists of two integers x_i and y_i, which indicate the location of the i-th ruin is x_i east and y_i north from a certain location in the zone. You can assume the following things for the ruins:

• −10⁹ ≤ x_i, y_i ≤ 10⁹
• You can ignore the sizes of ruins. That is, you can assume ruins are points.
• No pair of ruins has the same location.

출력

Print the minimum total preservation cost yielded by drawing an appropriate straight line. You should round off the cost to the nearest integer.

제한

힌트