SpaceProbes
TCO19 SRM 746 · 2019-01-09 · by majk
Problem Statement
In this problem we find ourselves in the standard three-dimensional space. We have two space probes. Each of them is capable of flying back and forth arbitrarily, but only along a single straight line. The line for the first probe is determined by the points [x[0],y[0],z[0]] and [x[1],y[1],z[1]]. The line for the second probe is determined by the points [x[2],y[2],z[2]] and [x[3],y[3],z[3]]. The two probes can move independently of each other.
The probes are equipped with powerful scanners to observe planets. Your goal is to scan a mysterious planet Theta, located at [x[4],y[4],z[4]].
The midpoint of the line segment connecting the two probes is called the focus point of their scanners. The precision of scanning decreases with the distance of the scanned object from the focus point. Hence it is crucial to position the probes in such a way that the distance between the focus point of the scanners and the planet Theta is minimized. Compute and return this minimal distance.
Notes
- For the purpose of this problem, the two probes and the planet are points. All three objects may share the same location.
- Your answer will be considered correct if its relative or absolute error is at most 10-6.
Constraints
- x, y and z will have 5 elements each.
- Each element of each of the arrays will be between -1012 and 1012, inclusive.
- The five points [x[i], y[i], z[i]] will be distinct.
{0,1,2,3,4}
{5,6,7,8,9}
{12,6,4,2,5}
Returns: 0.0
The first probe moves along the line going through points [0,5,12] and [1,6,6], while the second one is on the line through [2,7,4] and [3,8,2]. In an optimal solution, we move the first probe to [-1.5, 3.5, 21] and the second one to [9.5, 14.5, -11]. The focus point will be located at [4,9,5], which coincides with the planet Theta's location. Hence the answer is 0.0.
{2,6,4,5,5}
{-1,7,7,4,7}
{8,8,2,4,2}
Returns: 2.23606797749979
In the optimal solution, the first probe should be located at [14/3, 13/3, 8] and the second probe at [8/3, 11, -2/3]. The focus point is then at [11/3, 23/3, 11/3]. The distance between the focus point and the planet Theta located at [5,7,2] is sqrt( (4/3)^2 + (2/3)^2 + (5/3)^2 ) = sqrt(45/9) = sqrt(5).
{0,-2,1,4,0}
{-1,-999999999998,1,999999999997,0}
{-1,1000000000000,1,-999999999998,-2}
Returns: 0.8660254037861707
{0,0,0,0,0}
{1,2,3,4,5}
{1,4,9,16,25}
Returns: 0.0
{3,-4,-5,-6,3}
{2,1,2,1,2}
{4,3,1,5,6}
Returns: 0.03329635791060134
{0,1,0,-1,4}
{0,0,9,9,4}
{0,0,0,0,4}
Returns: 4.031128874149275
Test against people who, in the 1D case, incorrectly construct the line as passing through (A+C)/2 and (B+D)/2, as that is the same point here.
Submissions are judged against all 114 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SpaceProbes with a public method double focusDistance(vector<long long> x, vector<long long> y, vector<long long> z) · 114 test cases · 2 s / 256 MB per case