Perimeter of the Hay Bales

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 50000 grid cells forming one connected region, find the outer perimeter, ignoring any enclosed holes.

Level: Medium6 of 10
Topics: Graph, BFS, Hash map, Geometry
Solved: No attempts yet

Problem

A farmer has arranged N hay bales (1 ≤ N ≤ 50000) in a field. Model the field as a 1,000,000 × 1,000,000 grid of unit square cells; each hay bale occupies exactly one cell, and no two bales occupy the same cell.

The bales form a single connected region: starting from any bale, you can reach every other bale by repeatedly stepping north, south, east, or west onto a directly adjacent bale. The region may enclose holes — empty areas that are completely surrounded by bales.

Compute the perimeter of the region formed by the bales. Holes do not contribute to the perimeter.

Input

The first line contains the integer N, the number of hay bales.
Each of the next N lines contains two integers x and y (1 ≤ x, y ≤ 1,000,000): the location of one hay bale. Cell (1, 1) is the lower-left corner of the field and cell (1000000, 1000000) is the upper-right corner.

Output

Print a single integer: the perimeter of the connected region of hay bales.

Notes

Consider the following arrangement of bales (X marks a bale, a blank marks an empty cell):

XX
X XX
XXX

The outer perimeter of this region has length 14 — for instance, the left side contributes a length of 3. The single empty cell enclosed in the middle is a hole, so it does not add to the perimeter.

Examples2

Example 1

Input

8
10005 200003
10005 200004
10008 200004
10005 200005
10006 200003
10007 200003
10007 200004
10006 200005

Expected output

Example 2
Input
```
1
1 1
```
Expected output
```
4
```