Konijntje's blog

By Konijntje, history, 3 years ago, In English

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.

  • Vote: I like it
  • +108
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Konijntje (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +110 Vote: I do not like it

Can we include floating point error analysis as a requirement in the guideline for contest problems?

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Here is the solution I wrote back then: https://pastebin.com/X0y17sCL. It gives the following answers: 0.0001059175, 0.0000030389. So the first test breaks author solution. Sorry I didn't analyze precision issues when prepared the problem. The problem was supposed to be simple and making coordinates/radius up to 10^9 was wrong (10^6 would be fine for this problem). I attached this post to the contest as an additional editorial.