Earth and The Meteorites

3.8

191 votes
Approved, Easy, Ready, Sorting
Problem

Once upon a time, the Earth was a flat rectangular landmass. And there was no life. It was then that the sky lit up with meteorites falling from out of space. Wherever they fell on the planet, a river was born, which flowed in all 4 directions (North, East, West, South), till the waters reached the edge of the Earth and simply fell off into space.

Now, these rivers criss-crossed and divided the one huge landmass (Pangaea) into many smaller landmasses. Now the lifeless (there was no life, remember?), want to know the number of landmasses on the planet after all the meteorites have fallen. They also want to know the area of the smallest and largest landmass. Can you help the lifeless in this question?

Input:

First line contains T which is the number of test cases.

First line of every test case contains 3 integers N, M, Q where N and M are coordinates of the bottom right corner of the planet and Q is the number of meteorites.
The next Q lines contains the coordinates X, Y where each of the meteorites fell.

Output:

For each test case, output a line containing 3 integers indicating the number of regions, the minimum area and the maximum area.

Constraints:

  • 1 ≤ T ≤ 10
  • 2 ≤ N, M ≤ 105
  • 0 ≤ Q ≤ 105
  • 1 ≤ X ≤ N
  • 1 ≤ Y ≤ M
  • 0 ≤ sum of Q over all test cases ≤ 105

Scoring:

  • 2 ≤ N, M ≤ 10, 0 ≤ Q ≤ 10 : (30 pts)
  • 2 ≤ N, M ≤ 1000, 0 ≤ Q ≤ 1000 : (30 pts)
  • Original Constraints : (40 pts)

Note:

  • The Earth can be assumed to be a rectangle with top left point as (1,1) and bottom right point (N,M).
  • More than one meteorite may have landed at some point.
  • The rivers may be assumed to be flowing in very thin straight lines parallel to the edges of the planet.
Sample Input
1
5 5 2
2 3
4 4

Sample Output
9 1 4
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Refer to image below showing all the regions with individual areas.

Editor Image

?