TopCoder problem "RestoringPolygon" used in SRM 332 (Division I Level Two)



Problem Statement

    

A rectangular polygon is a polygon whose edges are all parallel to the coordinate axes. The polygon must have a single, non-intersecting boundary.

You are given several horizontal line segments. You may remove some of the given segments and add any number of vertical segments to construct a rectangular polygon. Your goal is to maximize the number of edges in the final polygon.

You will be given int[]s x1, x2, and y. (x1[i], y[i]) and (x2[i], y[i]) are the end points of the i-th line segment. The given segments will have no common points. Return the maximal number of edges in a polygon that can be constructed using the above method. If no polygon can be constructed, return 0.

 

Definition

    
Class:RestoringPolygon
Method:restore
Parameters:int[], int[], int[]
Returns:int
Method signature:int restore(int[] x1, int[] x2, int[] y)
(be sure your method is public)
    
 

Constraints

-x1, x2 and y will all contain the same number of elements.
-x1, x2 and y will each contain between 1 and 16 elements, inclusive.
-Each element of x1, x2 and y will be between -1000 and 1000, inclusive.
-Corresponding elements of x1 and x2[i] will not be equal.
-The line segments described by x1, x2 and y will not have common points.
 

Examples

0)
    
{1,2,3,1}
{2,3,5,5}
{1,4,2,0}
Returns: 8
In this case all segments can be the edges of the polygon. The resulting polygon has 4 horizontal and 4 vertical edges for a total of 8.
1)
    
{1,1,2,2}
{3,3,4,4}
{0,2,1,3}
Returns: 4
In this case either the first two segments or the last two segments can be used to construct a square.
2)
    
{1}
{2}
{1}
Returns: 0
One segment is not enough.
3)
    
{0,0,0}
{1000,1000,1000}
{0,1,2}
Returns: 4

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10012&pm=6402

Writer:

andrewzta

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Brute Force, Simple Search, Iteration