Problem S. 107. (April 2016)

S. 107. There are \(\displaystyle N\) (\(\displaystyle 1\le N\le 200\,000\)) trees on a huge grid (\(\displaystyle 10\,000\,000\times 10\,000\,000\)) with each tree occupying one square. A squirrel notices that it can reach any tree starting from an arbitrary tree by a series of jumps from a tree to an adjacent tree (two squares are adjacent if they share a common edge). Although the set of squares containing the trees form a connected region, this region may contain holes (i.e., empty squares). Determine the length of the outer boundary of the forest (that is, without the holes).

Your program should read the value of \(\displaystyle N\) from the first line of the standard input, then the tree coordinates (\(\displaystyle 1\le x, y\le 10\,000\,000\)) from the next \(\displaystyle N\) lines. The first and only line of the standard output should contain the length of the outer boundary.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file s107.zip.

(10 pont)

Deadline expired on May 10, 2016.

Statistics:

10 students sent a solution.
10 points:	Kiss Gergely, Nagy Ábel, Nagy Nándor, Szakály Marcell.
8 points:	1 student.
6 points:	1 student.
5 points:	2 students.
4 points:	1 student.
3 points:	1 student.

Problems in Information Technology of KöMaL, April 2016