CLMNTR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Nibir Pal
Tester: Soumyadeep Roy
Editorialist: Soumik Sarkar

DIFFICULTY:

Medium

PREREQUISITES:

Mathematics, 2D geometry

PROBLEM:

Given the positions and radii of 3 spheres S, A and B, the task is to determine if the umbra of the shadow of A falls on B when S is the light source.

EXPLANATION:

There may be several ways to solve this mathematical problem. One such method is described below.

First, we realise that although we’re dealing with spheres, we can simply consider the problem in 2D by taking the cross sections of the spheres cut by the plane passing through their centres. Better yet would be to shift and rotate our axes as we please, as long as the relative distances between all 3 spheres remain same.Let,

sa = distance(S,A)
sb = distance(S,B)  
ab = distance(A,B).

Now let us choose to set S at (0,0) and A on the Y-axis. So, the coordinates of A must be (0,sa).
Let the coordinates of B be (bx,by).
We consider two circles, one centered at (0,0) of radius sb, and one centred at (0,sa) of radius ab. Thus (bx,by) is the intersection point of these two circles. Note that if there are 2 such points, either of them can be taken to find the answer, but we take the one with positive abscissa for convenience. So, the centre of B always ends up in the first or fourth quadrant. We use the formula here.

We get: by = (sa^2$-ab^2+sb^2)/2sa**. Next, we get **bx = sqrt(sbsb-by*$by).

We have all 3 circles in their proper places now. We check if B is in the fourth quadrant or B is closer to S than A. In both these cases, total solar eclipse is not possible.

Now, for total solar eclipse, B must partly or completely lie in the umbra region of A. This umbra region is bounded by the external tangents drawn from S to A. Proceeding, there are now 3 cases for us to consider, namely when A is smaller than S, when A is bigger than S, and when A and S are of equal size. Let us tackle the last case first.

When S and A are of equal size, the external tangents are parallel to each other and to the Y axis. Since our body B is always in the first quadrant, we only deal with the tangent passing through the first quadrant. The equation of this tangent is: x=rS. There is surely a total solar eclipse if the centre of B lies to the left of this tangent. There is also a total solar eclipse if distance of B from this tangent is less than rB.
Otherwise, there is no total solar eclipse.

In both the other cases, we will need to determine the tangent passing through the first quadrant with the help of formulae. Let our required tangent t be y=mx+c where m is its slope and c its Y intercept.

Then:
distance(S,t) = rS and distance(A,t) = rA.
Distance of a point (a,b) from a line (y=mx+c) = |ma-b+c|/sqrt(m^2+1).
We get |c|/sqrt(m^2+1) = rS and |c-sa|/sqrt(m^2+1) = rA.
Solving, we get c^2/rS^2 = (c-sa)^2/rA^2.
This leads to two solutions, c = rSsa/(rS-rA) and c = rSsa/(rS+rA).

The former is for external tangents, the latter for internal tangents.
Now we find m = sqrt(c^2/rS^2-1). If our c is positive, our slope is surely negative, and vice versa. Now we repeat what we did with the first case. If the centre of B lies to the left of our tangent t or if distance(B,t) is less than rB, we have a total solar eclipse.

However, a tricky cases arises from antiumbra cases when A is smaller than S. B may be beyond the umbra, but does intersect our tangent in the second quadrant. To eliminate these false positives, we check if distance(S,B) is greater than c+rB. Since (0,c) is the farthest point of the umbra, any body whose no part lies closer to S than c cannot lie in the umbra.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.