Connection Status:
Competition Arena > NoRightTurnDiv2

NoRightTurnDiv2

SRM 652 · 2015-01-29 · by lg5293

SRM 652 · 2015-01-29 · by lg5293 · Brute Force, Geometry
Class Name: NoRightTurnDiv2
Return Type: int[]
Method Name: findPath
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Roger the Robot has been sent to explore a planet. The surface of the planet can be thought of as a two-dimensional plane. You are given two int[]s x and y. The planet has N interesting points described by these int[]s. The i-th interesting point has coordinates (x[i], y[i]). No three interesting points will be collinear.

Roger will choose a permutation of {0,1,...,N-1}, and will visit the points in that order. Roger will travel in a straight line in between points. There are two conditions he must follow:

  1. He must never cross his own path (that is, if we look at the line segments formed by the path, no two segments strictly intersect).
  2. Due to rather unfortunate oversight, Roger is incapable of making any right turns. This means that for any three consecutive points that he visits, these three points constitute a counter-clockwise orientation.

Your job is to find a path that Roger can take. If there is no valid path, return an empty int[]. Otherwise, return an int[] containing a permutation of 0,...,N-1, representing a valid path that Roger can take.

Constraints

  • x will contain between 2 and 50 elements, inclusive.
  • y will contain exactly the same number of elements as x.
  • Each element of x,y will be between -1,000 and 1,000, inclusive.
  • All pairs (x[i], y[i]) will be distinct.
  • No three points will be collinear.
Examples
0)
{-10, 0, 10}
{10, -10, 10}
Returns: {0, 1, 2 }

The points form a triangle. Any of the following return values will be accepted: {0,1,2},{1,2,0},{2,0,1}

1)
{0,0,-3,-3,3,3}
{-1,1,-3,3,-3,3}
Returns: {0, 4, 5, 3, 2, 1 }

Here is a picture of the points: Here is an example of a different valid solution. This would correspond to a return value of {1,5,3,2,4,0}

2)
{10,9,8,7,6,5,4,3,2,1}
{1,4,9,16,25,36,49,64,81,100}
Returns: {9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }
3)
{0, 2,-2, 4,-4, 2,-2, 0}
{1, 2, 2, 4, 4, 6, 6, 5}
Returns: {4, 2, 0, 1, 3, 5, 6, 7 }
4)
{-76,98,83,58,-15,94,21,55,80,84,-39,-90,-46,100,-80,-49,-2,-70,36,48,88,10,
55,-56,22,67,31,81,100,-39,64,-62,-7,45,-82,-24,51,-33,53,11,20,-74,-83,47,
9,39,42,63,-97,94}
{-90,68,91,-92,-6,88,99,10,39,-69,-61,-4,71,-5,90,-51,21,-53,-21,-86,41,-9,
42,-23,-4,12,94,-59,55,18,70,-88,-86,-17,-97,-33,87,80,91,-80,-79,-79,-78,
-99,57,67,-52,-46,61,-10}
Returns: {39, 32, 40, 31, 19, 27, 47, 46, 0, 34, 43, 3, 9, 13, 28, 1, 5, 2, 6, 14, 48, 42, 41, 49, 20, 38, 26, 37, 12, 11, 17, 10, 33, 25, 8, 30, 36, 44, 29, 23, 15, 18, 7, 22, 45, 16, 4, 35, 24, 21 }

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

Coding Area

Language: C++17 · define a public class NoRightTurnDiv2 with a public method vector<int> findPath(vector<int> x, vector<int> y) · 80 test cases · 2 s / 256 MB per case

Submitting as anonymous