Problem Statement

You are given a set of two-dimensional vectors in two int[]s - x and y (the i-th elements of x and y represent x and y coordinates of the i-th vector). Find a subset of the vectors such that the sum of all vectors in the subset has the maximum possible length. Return this length.

Definition

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

Notes

• The sum of vectors (x1, y1) and (x2, y2) is the vector (x1+x2, y1+y2).
• The length of vector (x, y) is the value sqrt(x * x + y * y).
• The returned value must be accurate to within a relative or absolute value of 1E-9.
• The input (as well as the resulting subset) can contain equal vectors (see example 1).
• Consider the entire set to be a subset.

Constraints

• x will contain between 1 and 50 elements, inclusive.
• x and y will contain the same number of elements.
• Each element of x will be between -1000 and 1000, inclusive.
• Each element of y will be between -1000 and 1000, inclusive.

Examples

0)

{0,0}
{1,-1}
Returns: 1.0
Choose any one vector.

1)

{0, 0}
{1, 1}
Returns: 2.0
Choose two vectors. The sum is (0, 2).

2)

{0, 0, 1, -1}
{1, -1, 0, 0}
Returns: 1.4142135623730951

3)

{0, 0, 0, 0}
{1, 2, -1, -2}
Returns: 3.0

4)

{17,8,-5,-8,-8,-11,-3,2,19,4,22,15,20,13,-7,15,-23,17,-9,-10,17,24,20,-22,-1,-7,-19,18,-17}
{7,-5,-2,18,-9,-24,14,9,-21,14,-23,7,14,23,23,17,17,22,-3,-21,-10,1,24,-17,25,12,-21,12,13}
Returns: 289.4563870430224

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)2003, TopCoder, Inc. All rights reserved.

Google India Code Jam 2006 - Table of Contents

1. Main Page - Google India Code Jam 2006
2. Qualification Round
   • Set 1,10,13,16,25,28 :: Problem 250: ExamQuestions; Problem 1000: UnNestable
   • Set 2,9,15,20,21,27 :: Problem 250: GeneralElection; Problem 1000: UnNestable
   • Set 3,8,11,19,23,26 :: Problem 250: Sort01; Problem 1000: UnNestable
   • Set 4,7,14,18,22,29 :: Problem 250: PatternFiller; Problem 1000: PerfectNumbers
   • Set 5,6,12,17,24,30 :: Problem 250: TowerLifts; Problem 1000: PerfectNumbers
3. Elimination Round
   • Problem 250: MatrixConstructor
   • Problem 500: PalindromesAnalyzer
   • Problem 1000: VectorSet
4. Championship Round
   • Day 1, Take off to Bangalore, India (April 6, 2006)
   • Day 2, Code Jam Contest (April 7, 2006)
     • Breakfast and Google Tech Talk 1
     • The Contest Begins!!
       • Problem 300: InverseLca
       • Problem 500: ColoredDominoes
       • Problem 1000: InterestingString
     • Le Meridien and Google Tech Talk 2
     • Awards Winner announcements
     • Google Tech Talk 2 (continued) and dinner
   • Day 3, Interview with Google (April 8, 2006)
5. Links/Blogs/News