NoRightTurnDiv2 | Topcoder Archive

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:

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

Definition

Class:: NoRightTurnDiv2
Method:: findPath
Parameters:: int[], int[]
Returns:: int[]
Method signature:: int[] findPath(int[] x, int[] y)
(be sure your method is public)

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

```
{-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}
```
{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}

{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 }

{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 }

{-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 }

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.