ZOJ Problem Set - 2605
In a game of Civilization III the area controlled by a city is defined by its culture level. The game proceeds on a rectangular grid. A city occupies one grid square. Each city has a culture level which is a non-negative integer number.
A city with a culture level 0 controls its own square and eight adjacent squares. A city with a culture level 1 additionally controls all squares that share a side with those squares (a total of 9 + 12 = 21 squares). Generally, if a city with a culture level i controls the set A of squares, a city with the same location and a culture level i + 1 would control all these squares and also squares that share a side with at least one square from A.
The picture on the left shows the sets of squares controlled by cities with culture levels of 0, 1 and 2.
The area controlled by the civilization is defined as follows. Consider the total area controlled by all its cities. The civilization area is the smallest set of squares, such that it contains all the squares controlled by some city, and its complement contains no hanging squares. A square x of a set B is called hanging if there is no 2 * 2 square in B that contains square x.
Calculate the total area controlled by a civilization, given the locations of all its cities on a map. You may consider that the map is infinite and that there are no other civilizations.
The input consists of several test cases. In each case, the first line contains an integral number n - the number of the cities of a civilization (1 <= n <= 50). Next n lines describe cities. Each city is described with its integer coordinates (xi, yi) and its culture level ci. Coordinates do not exceed 109 by their absolute value, culture level does not exceed 10. The input ends up with a case where n = 0. Do not proceed this case.
Output the total number of squares controlled by a civilization, each case in a single line.
2 0 0 1 4 -3 0 0
NOTE: The squares controlled by the civilization in the example are shown on the right picture. The square marked by a small circle is not controlled by any city, however it belongs to the area controlled by the civilization because otherwise it would be hanging.
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #7