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 #cf_span(class=[tex-font-style-underline], body=[box hedge]), such that the following conditions are fulfilled:
The #cf_span(class=[tex-font-style-underline], body=[circumference]) of the box hedge is the number of edges separating outside tiles with the box hedge.
The #cf_span(class=[tex-font-style-underline], body=[size]) of the box hedge is the number of tiles contained in the box hedge.
The #cf_span(class=[tex-font-style-underline], body=[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 < = 106.
Each of the following N lines contains two coordinates x and y ( - 109 ≤ x ≤ 109 and 0 ≤ y ≤ 109).
It is guaranteed that no two attractions have the same coordinate.
Print a single line containing three numbers: the minimum circumference, size and area.
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"):
## Input
The first line contains an integer N, the number of attractions 1 < = N < = 106.Each of the following N lines contains two coordinates x and y ( - 109 ≤ x ≤ 109 and 0 ≤ y ≤ 109).It is guaranteed that no two attractions have the same coordinate.
## Output
Print a single line containing three numbers: the minimum circumference, size and area.
[samples]
## Note
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....BSSSSSSSSSSSSVVVVVVVVVVVVVVVVVVVVVVVV
**Definitions**
Let $ N \in \mathbb{Z}^+ $, $ 1 \leq N \leq 10^6 $, be the number of attractions.
Let $ A = \{ (x_i, y_i) \in \mathbb{Z} \times \mathbb{Z}_{\geq 0} \mid i \in \{1, \dots, N\} \} $ be the set of attraction coordinates, with all $ (x_i, y_i) $ distinct.
Let $ S \subseteq \mathbb{Z} \times \mathbb{Z}_{\geq 0} $ be a finite set of tiles (the *box hedge*), such that:
- $ A \subseteq S $,
- $ S $ is 4-connected,
- The complement of $ S $ in $ \mathbb{Z} \times \mathbb{Z}_{\geq 0} $ has exactly one unbounded connected component (exterior),
- All tiles with $ y = 0 $ (the street) are *not* in $ S $, and are part of the exterior.
Let:
- **Circumference** $ C(S) $: number of edges between $ S $ and its exterior,
- **Size** $ |S| $: number of tiles in $ S $,
- **Area** $ A(S) $: number of tiles in the bounded region enclosed by $ S $ (i.e., $ |\{ (x,y) \in \mathbb{Z} \times \mathbb{Z}_{>0} \mid (x,y) \notin S \text{ and enclosed by } S \}| $).
**Constraints**
1. $ A \subseteq S $
2. $ S $ is 4-connected
3. No tile with $ y = 0 $ is in $ S $
4. $ S $ encloses a single bounded region (no holes)
**Objective**
Find $ S^* \subseteq \mathbb{Z} \times \mathbb{Z}_{\geq 0} $ minimizing lexicographically:
$$
(C(S^*), |S^*|, A(S^*))
$$
subject to the constraints above.