TrianglePath | Topcoder Archive

Problem Statement

Given is a right triangle. The three vertices of the triangle are at (0, 0), (Xmax,0), and (0, Ymax).

Also given is a collection of N (not necessarily distinct) points that all lie inside or on the boundary of the triangle. Points are numbered 0 through N-1, with point i having coordinates (X[i], Y[i]).

Your task is to construct a polyline with the following properties.

The polyline visits each of the given points exactly once.
The sum of squares of lengths of the segments of the polyline must not exceed Xmax^2 + Ymax^2.

Return a permutation of 0 through N-1 that corresponds to one possible order in which the polyline should visit the N points. Any valid solution will be accepted If there is no solution, return an empty int[] instead.

The input is generated pseudorandomly as follows:

X = Xprefix
Y = Yprefix
state = seed
while length(X) &lt; N:
    state = (state * 1103515245 + 12345) modulo 2^31
    xnew = state modulo (Xmax + 1)
    state = (state * 1103515245 + 12345) modulo 2^31
    ynew = state modulo (Ymax + 1)
    if point (xnew, ynew) lies inside the triangle or on its boundary:
        X.append(xnew)
        Y.append(ynew)

Definition

Class:: TrianglePath
Method:: construct
Parameters:: int, int, int, int[], int[], int
Returns:: int[]
Method signature:: int[] construct(int N, int Xmax, int Ymax, int[] Xprefix, int[] Yprefix, int seed)
(be sure your method is public)

Notes

Note that one of the constraints implies that the triangle cannot be long and narrow, so there should not be any too-degenerate test cases.

Constraints

N will be between 1 and 3000, inclusive.
Xmax will be between 3 and 10^6, inclusive.
Ymax will be between 3 and 10^6, inclusive.
20*Xmax >= Ymax and 20*Ymax >= Xmax.
Xprefix will have between 0 and min(N,500) elements.
Yprefix will have the same number of elements as Xprefix.
Each point (Xprefix[i], Yprefix[i]) will lie inside the triangle or on its boundary.
seed will be between 0 and 2^31 - 1, inclusive.

Examples

```
3
```
```
40
```
```
30
```
```
{0, 40, 0}
```
```
{0, 0, 30}
```
```
47
```
```
Returns: {2, 0, 1 }
```
The three points are in the corners of the triangle. We can visit them in the order {1, 0, 2}. If we do so, the first segment of the polyline has length 40 and the second segment has length 30. This exactly satisfies the constraints, as 40^2 + 30^2 = 40^2 + 30^2. The reverse order {2, 0, 1} is also a valid solution, but the other four permutations are not. For example, if we visit the points in order {0, 1, 2}, the sum of squares of polyline segment lengths will be 40^2 + 50^2, which is too big.

{5, 2, 4, 1, 3}

{1, 4, 2, 5, 3}

Returns: {3, 1, 4, 2, 0 }

{47, 47, 47}

{47, 47, 47}

47474747

Returns: {0, 1, 2 }

```
10
```
```
12
```
```
14
```
```
{4, 7}
```
```
{7, 4}
```
```
1
```
```
Returns: {6, 5, 0, 8, 9, 3, 4, 7, 1, 2 }
```
The arrays X and Y you are supposed to obtain look as follows: X = {4, 7, 9, 0, 0, 1, 2, 5, 5, 4, }; Y = {7, 4, 0, 1, 0, 7, 11, 4, 5, 5, };

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.