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.



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


-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.


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.
Returns: 4
In this case either the first two segments or the last two segments can be used to construct a square.
Returns: 0
One segment is not enough.
Returns: 4

Problem url:

Problem stats url:




PabloGilberto , brett1479 , , Olexiy

Problem categories:

Brute Force, Simple Search, Iteration