Enclosing the Grid Points

Time limit5sMemory limit256 MB

Summary

Compute the shortest perimeter of a lattice polygon with axis-aligned and diagonal sides that encloses all given grid points strictly inside.

Level: Medium4 of 10
Topics: Geometry, Math
Solved: No attempts yet

Problem

Peter and Bob play a game on a sheet of graph paper. Peter marks a few grid nodes with points, and Bob draws a polygon around them. Every marked node has to lie strictly inside the polygon, never on its border. Every side of the polygon lies along a side or a diagonal of a grid cell, and the perimeter is as short as possible. Compute that perimeter.

Input

The first line contains the number of points Peter marked, $N$ ( $1 \le N \le 100\,000$ ). Each of the next $N$ lines contains two integers $x_i$ and $y_i$ , the coordinates of one point. Each coordinate has absolute value at most $10^6$ . Several points can share the same coordinates.

Output

Print the perimeter of the polygon on one line, rounded to exactly six digits after the decimal point.

Examples3

Example 1
Input
```
1
0 0
```
Expected output
```
5.656854
```
Example 2
Input
```
2
1 1
1 2
```
Expected output
```
7.656854
```
Example 3
Input
```
4
0 0
0 3
3 0
3 3
```
Expected output
```
17.656854
```