RestoringPolygon | Topcoder Archive

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

```
{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,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.
```
{1}
```
```
{2}
```
```
{1}
```
```
Returns: 0
```
One segment is not enough.

{0,0,0}

{1000,1000,1000}

{0,1,2}

Returns: 4

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.