Connection Status:
Competition Arena > SpiralConstruction

SpiralConstruction

SRM 373 · 2007-10-23 · by Vedensky

SRM 373 · 2007-10-23 · by Vedensky · Dynamic Programming
Class Name: SpiralConstruction
Return Type: int
Method Name: longestSpiral
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Given a set of points, choose the maximal number of them that can be used to form a spiral.

A spiral is formed as follows:

1. Start at point (0, 0).
2. Draw a line segment from the current point to one of the given points (x, y). (x, y) is now the new current point.
3. Repeat step 2 as many times as possible while obeying the following rules:
  • The spiral must not intersect itself. This means that no two line segments in the spiral can have any common points (except the common endpoints of neighboring segments).
  • Each point must not be used more than once.
  • When going from each line segment to the next, you must turn counterclockwise and go forward. The angle you turn must be greater than or equal to 0, and strictly less than 180 degrees.
  • The ray that originates from the second to last point and goes through the last point must not intersect any of the other line segments in the spiral.


These three spirals do not satisfy the first, second and third rules:

These two do not satisfy the fourth rule:


You are given a String[] points, each element of which represents a single point whose coordinates are given as "X Y" (quotes for clarity). Return the maximal number of points that can be used to form a single spiral.

Constraints

  • points will contain between 1 and 15 elements, inclusive.
  • Each element of points will be formatted as "X Y" (quotes for clarity), where X and Y are integers with no extra leading zeros.
  • Each X and Y will be between -1000 and 1000, inclusive.
  • All elements in points will be distinct.
  • There will be no "0 0" in points.
Examples
0)
{"0 1", "1 0"}
Returns: 2

(0,0) -> (1,0) -> (0,1) is a valid spiral.

1)
{"1 1", "2 2", "-1 -1"}
Returns: 2

(0,0) -> (1,1) -> (2,2) is the longest valid spiral. Note that there is a turn by 0 degrees.

2)
{"0 1", "2 2", "-2 2", "-2 -2", "2 -2", "1 1"}
Returns: 6
3)
{"0 1", "1 1", "0 2"}
Returns: 2

You can't form a valid spiral using all three points.

4)
{"4 -2", "2 2", "-5 6", "-7 8", "-9 -1", "3 0", "8 8", "-2 -4",
 "-4 -7", "-4 -1", "-1 -9", "-5 3", "4 9", "2 6", "-2 5"}
Returns: 15

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

Coding Area

Language: C++17 · define a public class SpiralConstruction with a public method int longestSpiral(vector<string> points) · 56 test cases · 2 s / 256 MB per case

Submitting as anonymous