cho.sh

Share the Ruins Preservation

Split points by a vertical line that avoids all points, build the minimum-area enclosing convex hull of each side, and minimize the total area.

Hard8GeometrySortingDivide and conquerImplementationNo attempts yetTime limit2sMemory limit512 MB

Problem

Two organizations, the International Community for Preservation of Constructions (ICPC) and the Japanese Archaeologist Group (JAG), preserve ruins. 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 rest to JAG.

ICPC and JAG use the following rule for the assignment.

  1. Draw one vertical straight line running from north to south. The line must not pass through any ruin.
  2. Ruins to the west of the line are preserved by ICPC, and ruins to the east of the line are preserved by JAG. A side of the line may hold no ruins at all; in that case the corresponding organization preserves nothing.

The question is where to draw the line. Each organization preserves its assigned ruins by building exactly one fence such that all of its assigned ruins lie in the region surrounded by the fence, and to save budget it makes that fence as short as possible. Maintaining the inside of a large surrounded region is expensive, so the two organizations want to minimize the total preservation cost, that is, the sum of the areas surrounded by the two fences.

Write a program that computes the minimum possible sum of the areas surrounded by the two fences over all valid positions of the line.

Input

The input consists of a single test case.

N
x1 y1
...
xN yN

The first line contains an integer NN (1≤N≤100,0001 \le N \le 100{,}000), the number of ruins found. Each of the following NN lines gives the location of one ruin: the ii-th of them contains two integers xix_i and yiy_i, meaning that the ii-th ruin is xix_i east and yiy_i north of a reference point in the zone. You may assume the following about the ruins.

  • −109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9
  • The sizes of the ruins can be ignored, so each ruin is a point.
  • No two ruins are at the same location.

Output

Print the minimum total preservation cost, that is, the minimum sum of the areas surrounded by the two fences over all valid lines. The sum is always an integer or an integer plus 0.50.5. Print it rounded to the nearest integer, rounding a fractional part of exactly 0.50.5 up.