Problem C
Office Space

Your company is moving to a new, larger office building. The new office is a rectangular space that will eventually be populated with cubicles. Your employees want to request particular positions for their cubicles, so you are setting up a system that lets them make these requests. To help automate this process, you have expressed the new office building using a coordinate system where each unit is one foot. The south-west corner of the new building’s floor space is assigned coordinate $(0, 0)$, the positive $X$ axis is aligned with the inner edge of the building’s south wall and the positive $Y$ axis is aligned with the west wall. Employees request a position for their cubicle by giving the coordinates of the cubicle’s south-west corner and its north-east corner.

You don’t expect this technique for dividing up the space to work very well the first time around. Some space may not get allocated and space may be requested by more than one employee. Your job is to compile a report of how well these requests would allocate the office space and how much contention there is between requests.

\includegraphics[width=0.5\textwidth ]{space}


Input consists of up to $10$ test cases. Each case starts with a line containing a pair of integers $w$ and $h$ giving the size of the new office space ($w$ is the number of feet west-to-east; $h$ is the number of feet south-to-north). Both of these numbers are in the range $1 \ldots 100$. After this is a line containing an integer $0 \le n \le 20$ giving the number of employees you have. Following this are $n$ cubicle placement requests, one per line. Each request starts with the name of the employee. The name is a string of $1$ to $20$ lower- and/or upper-case letters (a–z). The name is followed by four integers $x_1, y_1, x_2, y_2$ where $(x_1, y_1)$ indicate the coordinates of the south-west corner of their desired cubicle placement and $(x_2, y_2)$ indicate the coordinates for the north-east corner. Each set of request coordinates satisfies $0 \le x_1 \le x_2 \le w$ and $0 \le y_1 \le y_2 \le h$. The sequence of test cases ends at the end of file.


For each test case, print out a report that starts with the total number of square feet in the building and the number of square feet that no employee has requested (the unallocated space). Next, give the total number of square feet that are contested because more than one employee has requested the same region of the floor. Finally, for each employee give the number square feet that that employee can be guaranteed to have. This is the total area that they requested minus any regions that were also requested by another employee. List the employees in the same order they were given in the input. Leave a blank line after the output for each test case.

Sample Input 1 Sample Output 1
33 26
Alice 2 3 10 11
Ted 7 2 18 8
GreedyBob 17 11 30 24
20 10
Employee1 0 0 9 10
Employee2 11 0 20 10
Total 858
Unallocated 574
Contested 15
Alice 49
Ted 51
GreedyBob 169

Total 200
Unallocated 20
Contested 0
Employee1 90
Employee2 90

Please log in to submit a solution to this problem

Log in