Connection Status:
Competition Arena > RestoringPolygon

RestoringPolygon

SRM 332 · 2006-12-28 · by andrewzta

SRM 332 · 2006-12-28 · by andrewzta · Brute Force, Simple Search, Iteration
Class Name: RestoringPolygon
Return Type: int
Method Name: restore
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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
4)
{0,0,3,3}
{1,1,4,4}
{0,1,2,3}
Returns: 4

Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RestoringPolygon with a public method int restore(vector<int> x1, vector<int> x2, vector<int> y) · 113 test cases · 2 s / 256 MB per case

Submitting as anonymous