TopCoder problem "MissileTarget" used in SRM 258 (Division II Level Three)



Problem Statement

    

You are working for a defense agency that is testing the accuracy of a new missile guidance system. As part of this effort, several missiles have been fired off. Each missile fired was programmed with the same target coordinates, although the actual points of impact vary.

Your task is to determine the "best fit" point to describe the location where the missiles actually landed. To determine how well a point describes the location, calculate the cartesian distance from the point to each of the landing points. Then, total the sum of the squares of these distances. The best fit point is the point that minimizes this sum.

You are given int[]s x and y, both containing the same number of elements, where the i-th element of x and the i-th element of y describe the coordinates of the i-th missile landing point. You are to return a int[] with exactly two elements, describing the coordinates of the lattice point (point with integral coordinates) that is closest to the "best fit" point. The first element should be the x-coordinate, and the second element should be the y-coordinate.

 

Definition

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

Notes

-The cartesian distance between two points (x1, y1) and (x2, y2) is defined as Sqrt((x2-x1)^2 + (y2-y1)^2).
-The return value must be within 1e-9 absolute or relative error of the actual result.
 

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 -1000000 and 1000000, inclusive.
-Each element of y will be between -1000000 and 1000000, inclusive.
-The actual (possibly non-lattice) best fit point will be at least 1e-2 closer to the correct return value than to any other lattice point.
 

Examples

0)
    
{750, -500, -250}
{-1000, 500, 500}
Returns: {0, 0 }
These three impacts are all pretty close to the origin, and sure enough, the origin is the best fit point.
1)
    
{765}
{834}
Returns: {765, 834 }
With only one point, it is its own best fit.
2)
    
{100, 200}
{200, 400}
Returns: {150, 300 }
With only two points, the best fit is the midpoint between the two.
3)
    
{123456, -987654, 97531, -86420}
{14703, 25814, 36924, -47036}
Returns: {-213272, 7601 }
4)
    
{0, 5, 5, 6, 8, 8}
{0, 0, 0, 0, 0, 0}
Returns: {5, 0 }
In this case, notice that the actual best fit point possible is (5.333, 0). If we look at lattice points only, then our best fit is (6, 0), however, we are interested in the lattice point that is closest to the actual best fit point, so we return (5, 0).

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4705

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7993&pm=4705

Writer:

timmac

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Math, Search