TopCoder problem "CoolRectangles" used in SRM 362 (Division I Level Three)



Problem Statement

    You're given several rectangles in the cartesian plane with sides parallel to the coordinate axes. A "cool rectangle" is a rectangle in the plane such that each of its edges completely lies on the edges of some input rectangles (these edges may overlap). You want to "compress" the input rectangles by shrinking them into cool rectangles (this will happen instantaneously).



To compress an input rectangle into a cool rectangle, the interior of the cool rectangle must be completely contained within the input rectangle. The interiors of the chosen cool rectangles must not overlap (though their edges may touch), and each cool rectangle may compress at most one input rectangle. Determine the smallest total area of cool rectangles required to shrink all the input rectangles, or return -1 if it is impossible.



The input rectangles will be described by int[]s x1, y1, x2, and y2, where (x1[i],y1[i]) and (x2[i],y2[i]) are opposite corners of the ith rectangle.
 

Definition

    
Class:CoolRectangles
Method:compress
Parameters:int[], int[], int[], int[]
Returns:int
Method signature:int compress(int[] x1, int[] y1, int[] x2, int[] y2)
(be sure your method is public)
    
 

Constraints

-x1 will contain between 1 and 30 elements, inclusive.
-x1, y1, x2, and y2 will contain the same number of elements.
-Each element of x1, y1, x2, and y2 will be between -10000 and 10000, inclusive.
-For each rectangle, x1[i] < x2[i], and y1[i] < y2[i].
 

Examples

0)
    
{0,1,2}
{0,1,2}
{1,2,3}
{1,2,3}
Returns: 3
We have three non-overlapping squares, so the only cool rectangles are the input rectangles.
1)
    
{0,1}
{0,1}
{2,3}
{2,3}
Returns: -1
The overlapping squares generate 3 cool rectangles. However, there is no way to choose 2 non-overlapping cool rectangles to use.
2)
    
{1,0}
{1,2}
{3,4}
{4,3}
Returns: 3
These rectangles intersect in a way that allows for cool rectangles of area 1 and 2 to be used (although there are 11 available cool rectangles).
3)
    
{0,1,1}
{0,1,1}
{2,3,2}
{2,3,2}
Returns: -1
4)
    
{0,-1,-2,-3}
{0,1,2,3}
{1,2,3,4}
{7,6,5,4}
Returns: 4
5)
    
{1011,-647,134,-2009,875,819}
{189,-1504,1830,-1383,-319,825}
{2530,1930,620,-805,1821,1054}
{1419,1224,2476,203,1982,2943}
Returns: 2325650

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8015

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10775&pm=8015

Writer:

eleusive

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Geometry, Graph Theory, Greedy, Math