olympia's blog

By olympia, 7 weeks ago,

This problem was quite interesting in my opinion, so I'll write a blog post about it (plus, I'm ecstatic to have solved a 2000 rating problem!). Like all computational geometry problems, there are edge cases. I'll list them out:

1) Two circles are inside one another.

2) Two circles are the same.

3) Two circles are externally tangent.

4) Two circles are internally tangent.

5) The two circles don't intersect.

1 is an easy fix. To determine if two circles are inside one another, one needs to compare the distance between two circles with the radii. If the distance between the centers of the circles plus the smaller radius is less than the bigger radius, we know the smaller circles lies inside the bigger circle. To convince yourself that this is true, look at the diagram.

2 is an even easier fix: if the two circles have the same centers and the same radii, then of course they're the same circle. Conversely, if they don't have the same radii (for example) or don't have the same center, they're clearly not the same.

3 is a standard trick that all competitive mathematicians have seen. If the sum of the radii of the two circles are equal to the distance between their centers, they are indeed tangent. It makes sense after looking at a diagram.

4 is essentially the same as 3, except this time they're externally tangent, so we have to check if the absolute value of the difference of the two radii are equal to the distance between the two radii. diagram

5 is the same as saying that the sum of the two radii are less than the distance between the centers. diagram makes it self explanatory.

Now, we've identified cases 1,2,3,4,5 but what to do if we reach these cases? In case 1, simply take the area of the smaller circle (recall that the area of a circle is $\pi r^2$)., In case 2, simply take the area of any circle. In case 3, the answer is 0, and in case 4, the answer is the area of the smaller circle. In case 5, it's pretty easy to see that the answer is 0 as well. Note that depending on implementation, several of these cases aren't really edge cases and can be taken care of on their own.

Now, we can solve the problem working from the assumption that the two circles do indeed intersect and one circle is not entirely contained in another. The diagram looks like this. I'll keep the same point names as in the diagram, but to make things slightly faster, I'll define some new things as well. Let $d$ be the distance between the centers of the two circles.

We can decompose the area between the two circles into two parts: the area that lies to the left of $AB$ and the area that lies to the right of $AB$. We'll start by finding the area that lies to the left of $AB$.This area is actually just the area of the sector $AO_2B$ minus the area of the triangle $AO_2B$ (this become apparent after looking at the diagram). We'll start by finding the area of the sector $AO_2B$. In order to find this area, we need two things: $\alpha$ (which is $\angle AO_2B$) and the radius of the circle, which is already known (let's assume WLOG that it's $r_1$). But how to find $\alpha$?. This requires a change in perspective. Look at the new diagram. Note that $\angle AO_2O_1 = \alpha/2$. This is because of the well-known fact that the radical axis $AB$ is perpendicular to $O_1O_2$. With this in mind, using the law of cosines, we know that:

$\cos \alpha/2 = \frac{r_1^2 + d^2 - r_2^2}{2r_1d}$

from which we can find $\alpha/2$, from which we can find $\alpha$. Aha! We can finally find the area of sector $AO_2B$, which is:

$r_1^2 \cdot \alpha$

But recall that we also need to find the area of $AO_2B$. This can be done using the handy formula that $[ABC] = \frac{1}{2} \cdot BC \cdot AC \cdot \sin (C)$. Therefore,

$[AO_2B] = \frac{1}{2} \cdot AO_2 \cdot BO_2 \cdot \sin O_2 = \frac{1}{2}r_1^2 \cdot \sin \alpha$

And we're done. We've found the area of the portion lying to the left of $AB$, and finding the area to the right is the exact same, except we need to replace $r_1$ with $r_2$.

If you'd like, you can view my submission (88982522) here.

Parting words:

• I referred to the area to the left of $AB$ and to the right to $AB$ but this is not entirely what it is. When we code it up, finding out whether it's to the left or right is a pretty stupid idea. Just use the formula and replace $r_1$ with $r_2$.

• A LOT OF THE EDGE CASES AREN'T REALLY EDGE CASES. I just put them here because there are probably alternative solutions to this problem in which these edge cases don't need to be covered. Also some edge cases overlap.

• I hope you liked this!

• +18

 » 7 weeks ago, # |   +1 I calculated an integral instead 75081372