404647: GYM101597 J Box Hedge

As a reward of your great performance at SWERC in Paris, you're offered a job to take care of the garden in Versailles.

The palace complex of Versailles is arranged as follows: The main building is the center of everything. On one side, there is the garden and on the other side there is the village of Versailles. Those two are separated by a straight street of infinite length.

Now to the garden itself. Most of it are flowerbeds and you have full control over them. At certain points, however, there are static attractions (monuments, fountains, small huts, bird cages, etc.). You can't change the positions of those.

You want to plant a box hedge that surrounds all attractions and contains the minimum area possible (you are very smart and figured that less area means less work).

Let's define the task formally. The garden consists of a grid of 1 × 1 tiles with coordinates (x, y), such that x is any integer and y is any non-negative integer (below the tiles at y = 0 there is the street). Two tiles are adjacent if they share an edge. We say tile a is S-connected to tile b if they both lie in S and are either adjacent or a is connected to a tile in S adjacent to b. You need to find a set of tiles, called box hedge, such that the following conditions are fulfilled:

• The box hedge is connected, i.e. all tiles of the box hedge are pairwise box-hedge-connected.
• The box hedge touches the street, i.e. at least one tile of the box hedge has y = 0.
• All attractions are surrounded. We define outside tiles as tiles S-connected to a tile strictly above the highest tile of the box hedge, where S are all tiles not part of the box hedge. All tiles which are neither part of the box hedge nor outside are called surrounded.

The circumference of the box hedge is the number of edges separating outside tiles with the box hedge.

The size of the box hedge is the number of tiles contained in the box hedge.

The area is the number of surrounded tiles.

Find a box hedge satisfying the conditions listed above that minimizes the circumference as first priority, its size as second priority and the area as third priority.

The first line contains an integer N, the number of attractions 1 <  = N <  = 10⁶.

Each of the following N lines contains two coordinates x and y ( - 10⁹ ≤ x ≤ 10⁹ and 0 ≤ y ≤ 10⁹).

It is guaranteed that no two attractions have the same coordinate.

Print a single line containing three numbers: the minimum circumference, size and area.

3
2 1
-1 2
2 4

18 16 14

The optimal box hedge looks like this (where "B" means "box hedge", "A" means "attraction", "." means "inside, but not attraction", "S" means "street" and "V" means "village"):

      BBB
      BAB
   BBBB.B
   BA...B
   B...AB
   B....B
SSSSSSSSSSSS
VVVVVVVVVVVV
VVVVVVVVVVVV