ConstructPolyline | Topcoder Archive

Problem Statement

You are given a set of line segments in 3D Cartesian space. By moving these segments around (but not rotating or reflecting them), you are to connect the ends of the segments together to form a single non-self-intersecting open polyline, such that the two ends of the polyline are as far apart as possible. Return the magnitude of the maximum Cartesian distance between the ends squared. See the notes section for definitions if needed.

The segments are given to you in 3 int[]s x, y and z. Line segment i has one end at (0, 0, 0) and the other at (x[i], y[i], z[i]).

Definition

Class:: ConstructPolyline
Method:: maximizeLength
Parameters:: int[], int[], int[]
Returns:: long
Method signature:: long maximizeLength(int[] x, int[] y, int[] z)
(be sure your method is public)

Notes

A polyline is a piecewise linear curve in 3D cartesian space defined on a sequence of points {a1, a2, ... , an} consisting of straight line segments connecting adjacent points in the sequence.
Except for adjacent segments touching at each point ai, the line segments may not touch or intersect each other.
The line segments in the polyline must have a one-to-one mapping onto the supplied line segments via translation.
The ends of the polyline are the points a1 and an.
Multiple line segments can spatially coincide in the input; these should be considered as distinct line segments.

Constraints

x, y and z will each contain between 1 and 50 elements, inclusive.
x, y and z will contain the same number of elements.
Each element of x, y and z will be between -10000 and 10000, inclusive.
The length of each line segment will be non-zero.

Examples

```
{10,15,-5,-10}
```
```
{20,5,-20,5}
```
```
{5,-5,0,15}
```
```
Returns: 3425
```
The vertices of an optimal polyline are at: (0, 0, 0) (15, 5,-5) (20, 25, -5) (30, 45, 0) (40, 40, -15) The order of the segments in this line is {1, 2, 0, 3}. The distance between the ends squared is 40^2 + 40^2 + (-15)^2 = 3425.

{51,23,350,-18,-69,200}

{-100,-50,1,45,-69,-70}

{211,-245,56,566,23,24}

Returns: 1559907

{1,-1,2,-2,3,-3,4,-4,5,-5,6,-6}

{0,0,0,0,0,0,0,0,0,0,0,0}

{0,0,0,0,0,0,0,0,0,0,0,0}

Returns: 1764

These segments all lie on the same straight line.

{-368,-473,135,50,-125,82,-204,272}

{401,-153,39,-283,-37,-40,-347,-358}

{-91,-271,450,427,359,396,359,92}

Returns: 8705702

{10,10,10}

{21,21,21}

{-5,-5,-5}

Returns: 5094

Duplicate segments are allowed.

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.