Problem Statement |
| | You have collected a number of data points, each consisting of an ordered triple of three integers. Unfortunately, you've lost the original data. However, before you lost the data, you calculated the Euclidean distances between each pair of points and recorded the square of each distance. Given the distances as a String[], dists, you are to find the original data points, if possible. Each element of dists will be formatted as a single space delimited list of integers. The ith integer of the jth element of dists will represent the square of the distance between the ith and jth points.
You should return a String[], the ith element of which represents the the ith data point as 3 single space delimited integers. Since distances are preserved under translation and rotation, the first element of the return should always be "0 0 0", and the second element should consist of 3 non-negative integers sorted in non-descending order. If there are multiple such returns, pick the one that is lexicographically first. For the purposes of this problem, one return is before another lexicographically if it has a lower integer in the first location for which the two differ. In other words, find the first element of the return that is different between the two, and then find the first integer in the two elements that differ, and compare them. If there is no set of points that could generate the given distances, return an empty String[]. |
| |
Definition |
| | | Class: | Reconstruct | | Method: | findPoints | | Parameters: | String[] | | Returns: | String[] | | Method signature: | String[] findPoints(String[] dists) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | dists will contain between 1 and 20 elements, inclusive. |
| - | Each element of dists will contain between 1 and 50 characters, inclusive. |
| - | Each number in dists will be an integer between 0 and 1000, inclusive, with no extra leading zeros. |
| - | Each element of dists will contain the same number of integers as there are elements of dists, separated by single spaces. |
| - | In dists, integer i of element j will equal integer j of element i. |
| - | In dists, integer i of element i will equal 0. |
| |
Examples |
| 0) | |
| | | Returns: { "0 0 0", "0 0 1" } | |
|
| 1) | |
| | {"0 2 2","2 0 2","2 2 0"} |
| Returns: { "0 0 0", "0 1 1", "-1 0 1" } | |
|
| 2) | |
| | {"0 33 25","33 0 84","25 84 0"} |
| Returns: { "0 0 0", "1 4 4", "3 -4 0" } | |
|
| 3) | |
| | | Returns: { } | | There are no three integers the sum of whose squares is 15. |
|
|