Recently, I am solving old Educational Codeforces problem and found this problem, 600D — Area of Two Circles' Intersection. This problem seems quite simple. Description simply says, calculate area of intersection of two area. This problem could be given as one excercise of 10th grade students' math class. What spice it up is real number and its error.
Solution of this problem is (when $$$r_1$$$ = $$$r_2$$$ = $$$R$$$ and $$$D = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$$)
$$$2R^2(\theta - \sin(\theta)\cos(\theta))$$$ where $$$\theta$$$ is given as $$$\cos^{-1}\left(\frac{D}{2R}\right)$$$.
Which seems quite simple, but you always have to aware of that minus. If there is minus in your formula, you should always be aware of it.
So, when does the error occur? Real error of $$$A-B$$$ occurs when $$$A$$$ and $$$B$$$ is close enough than $$$A$$$ or $$$B$$$. So, If $$$\frac{\theta-\sin(\theta)}{\theta} \sim O(\theta^2)$$$ is close enough to 0, than error will likely be happen. And they are close enough when $$$\theta$$$ is close to 0. Machine Epsilon of long double is $$$10^{-19}$$$. So if $$$\theta \sim 10^{-9}$$$, there likely will be real error.
Let's calculate how $$$\theta$$$ could be small. Let's rewrite $$$D = \sqrt{4R^2-v}$$$ and $$$\theta = cos^{-1}\left(\frac{\sqrt{4R^2-v}}{2R}\right) = \sin^{-1}\left(\frac{\sqrt{v}}{2R}\right) \sim \frac{\sqrt{v}}{2R}$$$. We can choose $$$v$$$ freely, so $$$\theta$$$ could be as small as $$$10^{-9}$$$. But in this case, answer is not large enough to make absolute error large.
To make absolute error large, $$$2R^2(\theta - \sin(\theta)\cos(\theta)) \sim 10^{-6}$$$, $$$10^{18} \times \theta^3 \sim 10^{-6}$$$ which is $$$\theta \sim 10^{-8}$$$. So, By having $$$v$$$ larger than $$$\sim 100 = (10^9 \times 10^{-8})^2$$$ we can exploit.
By using these strategy, We can carefully choose $$$v = 566$$$, $$$v = 6039$$$, and $$$R = 6 \times 10^8$$$ where $$$4R^2-v$$$ is representible as sum of two squares and exploit epsilon of $$$\cos^-1$$$ and $$$\sin$$$ calculation as possible as can. Here are the data:
Input
0 0 600000000
935404269 751677360 600000000
Output
0.00013036020766994
Input
0 0 600000000
976586705 697336653 600000000
Output
0.00000374043529189
Where output is calculated with mpmath library, with 300 digits precision. Most of solutions submitted and accepted failed to answer this.
If there are anything wrong or overly complex part, please write down into comment.
Edvard, please check this issue and solution, and if you can do an action such as changing eps, publish exact model solution, adding data above, and so on, please do so.
