ZOJ Problem Set - 3251
Usually, to distinguish different bacteria with naked eyes is impossible. You must reproduce them to a large enough magnification by the microscope. But in fact some bacteria can be distinguished by their bacteria colonies. A bacterial colony is a visible bunch of microorganisms that sprang from a single mother cell, and different bacteria colonies have their unique traits.
CM is an amateur biologist. In his lab, there are many kinds of bacteria, and he likes to do some research on them. Last week he found a strange bacterium called "copy triangle". Its colony grows like this:
The following pictures show how they grow.
CM wants to research the competence of this kind of bacteria, so after they fill up with the container, (it's infinite), he puts another kind of bacteria called "crazy grow" in some grids. If the grid is not occupied by "copy triangle" these bacteria will spread to neighbor grids (up, down, left and right) which are empty, or they will be eliminated by copy triangle immediately. Now he wants to know how many grids will be occupied by "crazy grow".
There are multiple test cases. The first line of input contains an integer T (T <=20), indicating the number of test cases. Then T test cases follow.
The first line of each test case contains an integer M, (0<M<=5000). CM puts "crazy grow" in M grids. Then M lines follow. Each line contains two integers Xi and Yi, which means that CM puts "crazy grow" in grids (Xi, Yi), (0<=Xi, Yi<=231-1).
For each test case, output how many grids are occupied by "crazy grow".
2 3 1 1 2 2 4 4 3 1 1 1 3 2 2
Author: HUANG, Minzhi
Source: ZOJ Monthly, September 2009