Dyson Circle

Time limit4sMemory limit1024 MB

Summary

Given n unit-square stars on a grid, find the fewest unit squares forming a corner-connected ring that encloses all stars without edge leaks.

Level: Hard8 of 10
Topics: Graph, Shortest path, Geometry
Solved: No attempts yet

Problem

A Dyson Sphere is a theoretical construction around the sun or another star that captures the entire energy output of the star. Science fiction writers have speculated that advanced civilizations will eventually build such a sphere, because the energy demands of such a society keep growing without bounds. In our three-dimensional space, Dyson spheres are still in the realm of fiction. Dy & Son, the main energy company of your dimensional neighbours, has tasked you with a feasibility study in the two-dimensional world of Flatland.

Dy & Son has developed a modular Dyson Circle. It consists of independent square Dyson Units that can chain together to form a closed loop that gathers energy. Your task is to find how many of these Dyson Units Dy & Son needs to enclose the star or stars they are interested in. They want a single Dyson Circle, not a separate one for each star.

For convenience, both the stars and the Dyson Units are modeled as squares of exactly $1$ by $1$ Intergalactic Unit, aligned to the Intergalactic Coordinate System. Dyson Units connect if they have at least a corner in common. See Figure 1 for an example.

Figure 1: Illustration of Sample Input 1: four stars (yellow squares) and an optimal Dyson Circle (dashed blue squares) surrounding them, and the remaining blackness of space shown in white.

Formally, select some squares in the plane to turn into Dyson Units, such that the remaining squares can be split into inside and outside squares. All the stars must be inside squares. The inside squares must form a contiguous region (connected via edges) and must not connect to the outside squares via edges. The outside squares form a contiguous region stretching off to infinity.

Input

The first line contains an integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ), the number of stars. Each of the next $n$ lines contains two integers $x$ and $y$ ( $-10^6 \leq x, y \leq 10^6$ ), the location of the center of a star. No two stars are at the same location.

Output

Output the least number of Dyson Units required to capture the energy of all stars in the input.

Examples3

Example 1
Input
```
4
2 5
-5 2
-2 -5
5 -2
```
Expected output
```
32
```
Example 2
Input
```
2
1 1
3 2
```
Expected output
```
8
```
Example 3
Input
```
2
2 3
4 5
```
Expected output
```
9
```