Connection Status:
Competition Arena > ConstructPolyline

ConstructPolyline

Member SRM 471 · 2009-12-03 · by StevieT

Member SRM 471 · 2009-12-03 · by StevieT · Brute Force, Geometry, Search
Class Name: ConstructPolyline
Return Type: long
Method Name: maximizeLength
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

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

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
0)
{1000,1000,1000,1,0,-1,10}
{0,1,-1,1000,1000,1000,-1}
{0,0,0,0,0,0,0}
Returns: 18066101
1)
{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.

2)
{51,23,350,-18,-69,200}
{-100,-50,1,45,-69,-70}
{211,-245,56,566,23,24}
Returns: 1559907
3)
{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.

4)
{100,71,0,-72,-101,-70,0,73,0,0,0,0,0,0}
{0,72,99,72,0,-72,-103,-71,0,0,72,-72,71,-73}
{0,0,0,0,0,0,0,0,-98,102,70,71,-73,-72}
Returns: 686558
70)
{10,10,10}
{21,21,21}
{-5,-5,-5}
Returns: 5094

Duplicate segments are allowed.

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

Coding Area

Language: C++17 · define a public class ConstructPolyline with a public method long long maximizeLength(vector<int> x, vector<int> y, vector<int> z) · 114 test cases · 2 s / 256 MB per case

Submitting as anonymous