레이팅 미적용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, as the energy demands of such a society continue to grow 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 carrying out 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 figure out how many of these Dyson units they actually need to enclose the star or stars they are interested in. Note that they want a single Dyson Circle, not a separate one for each star.
For convenience, both the stars Dy & Son wants to enclose and the Dyson Units used for this are modeled as squares of exactly \(1\) by \(1\) Intergalactic Unit, aligned to the Intergalactic Coordinate System. Your Dyson units connect if they have at least a corner in common. See Figure for an example.
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 not connect to the outside squares (via edges). The outside squares form a contiguous region stretching off to infinity.
The input consists of:
- One line with an integer \(n\) (\(1 \le n \leq 2 \cdot 10^5\)), the number of stars.
- \(n\) lines, each containing 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 the least number of Dyson units required to capture the energy of all stars in the input.
4
2 5
-5 2
-2 -5
5 -2
32
2
1 1
3 2
8
2
2 3
4 5
9