ZOJ Problem Set - 3133
There is a factory where grid panels are produced. Sometimes a newly made panel has some faults, which are holes at grid points of the panel. The workers in the factory gather all panels with faults, and then cut off the portions containing holes, finally replacing them with faultless pieces of panels. They have to cut along grid lines and remove a connected region containing all grid cells adjacent to each hole from a faulty panel. The connected region must satisfy the following conditions:
A polygon is said to be a rectilinear polygon if its boundary consists of horizontal or vertical line segments only. A rectilinear polygon is said to be a rectilinear convex polygon if its intersection with every horizontal or vertical line is either empty or a line segment.
For example, consider an 8 * 7 panel with 6 holes in Fig. 1(a). If the fourth row from the bottom is selected as a base cutting strip, a connected region with 29 grid cells is removed (see Fig. 1(b)). If the fourth column from the left is selected, a connected region with 27 grid cells is removed (see Fig. 1(c)), which is the smallest rectilinear convex polygon.
Given the dimensions of a panel and the positions of holes, write a program for computing the smallest rectilinear convex polygon satisfying the above conditions. Since the area of a grid cell is 1, the area of the rectilinear convex polygon in Fig. 1(c) is 27.
Your program is to read from standard input. The input consists of Ttest cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers w and h, the width and the height of a panel, 2 <= w, h <= 50,000. In the second line, an integer n (1 <= n <= 1,000) is given, where n is the number of holes. Each of the following nlines contains two integers x and y (0 <= x<= w, 0<= y<= h), where (x, y) represents the coordinate of a hole. Assume that the left-bottom corner of a panel is the origin of the coordinate system. There is a single space between the integers.
Your program is to write to standard output. Print exactly one line for each test case. Print an integer, the area of the rectilinear convex polygon which minimally covers all holes on the panel.
The following shows sample input and output for three test cases.Sample Input
3 4 4 1 2 2 8 7 6 2 2 3 1 8 3 5 5 4 6 3 4 12 10 15 2 7 3 8 4 6 4 7 5 5 5 7 6 4 6 5 7 3 7 5 8 2 8 3 9 4 9 5 10 3Sample Output
6 27 44
Source: Asia Regional Contest Seoul 2006