There are two ways you can solve this, and they are radically different. A key observation for both of them is that you can take the square root out of the problem, and simply look to see if the square of the distance between the two planes is less than or equal to the square of the threshhold. That simplifies the problem a bit.
Differentiate this and set it to zero. That's the value of t where the distance is minimized. Check this against the threshhold, and you're done. It will make your life easier to change some of those variables. For example, let x_{i} = p1[i]-p2[i] and let y_{i} = v1[i]-v2[i]. That will simplify those equations.
I have code for this solution in Solution-1.cpp.
Next, let's graph examples 0, 1 and 2 -- that may help us visualize a solution:
Example 0. |
Example 1. |
Example 2. |
Our goal is to find a value of t, which we'll call min, that minimizes S(t).
Our first observation is that if we find a value of high where S(high) > S(0), then min has to be less than high. That is because high will have to be on the increasing part of that graph, and values of t that are larger than high will have S(t) > S(high).
I found high by setting t equal to one, and then doubling it until S(t) > S(0). You can see those points on the graphs above.
Next, you are going to perform a binary search. You maintain two values: low and high, where you know that min has to be between them. You'll start with low equal to 0. You then successively move low and high towards each other, until they are so close that any answer would be in the roundoff error. At that point, you set min equal to one of them.
Here's how I did that. Suppose you have three points a, b and c, such that:
Minimium between b and c |
Minimium between c and high |
In this case, you can set low equal to b, and repeat the algorithm.
Similarly, if S(a), S(b) and S(c) are increasing, then you can set high to b.
Now, suppose that S(a) and S(b) are decreasing, and S(b) and S(c) are increasing. In that case min has to be between a and c, so you set low to a and high to c. Again, the following graphs will illustrate:
Minimium between a and b |
Minimium between b and c |
This gives us the information that we need to do the binary search. At each step, we set a, b and c so that divide the interval between low and high into four equal pieces:
The final piece of the puzzle involves roundoff error, and it's a bit unfortunate. You repeat this algorithm, narrowing the interval between low and high, until that interval is beneath a threshhold. I used 10^{-9} as that threshhold. At that point, you can calculate S(min) and see if it is less than or equal to R*R.
The unfortunate part is that because of roundoff error, you really need to check to see if it is within some threshhold of R*R. Again, I used 10^{-9} -- in other words, you need to check to see if S(min) is less than R*R + 10^{-9}. That handles the roundoff error. If you don't do that, you'll fail one of the cases in the system test. I'm guessing that may be the reason why the success rate here was so low.
I have a solution in this directory, but it is protected to be read-only, because I will probably give this as an in-class or honors lab.