### TL;DR↵
[problem:600D] requires careful treatment of loss of significance, more than the geometry itself. The test is plagued by the numerical errors, and rejects "more accurate" solution.↵
↵
↵
### Geometry ↵
Let's review the geometry, first. We need three numbers $(r_1, r_2, d)$; where $d$ is the distance between two centers,↵
↵
$$ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}. $$↵
↵
When two circles do not intersect, which is the case $d > r_1 + r_2$, the area of intersection is zero.↵
↵
When one circle is contained in the other, which is the case $\max(r_1, r_2) >= d + \min(r_1, r_2)$, the intersection equals to the smaller circle.↵
↵
↵
↵
Otherwise, intersection of two circles is determined from two circular sectors subtracted by two triangles, yielding↵
↵
$$ \mathrm{Intersection} = r_1^2 ( \theta_1 - \sin \theta_1 \cos \theta_1) + r_2^2 ( \theta_2 - \sin \theta_2 \cos \theta_2). $$↵
↵
where angles $\theta_1$ and $\theta_2$ are determined from the cosine formula↵
↵
$$\theta_1 = \cos^{-1} \left( \frac{r_1^2 + d^2 - r_2^2}{2 r_1 d} \right),$$↵
↵
$$\theta_2 = \cos^{-1} \left( \frac{r_2^2 + d^2 - r_1^2}{2 r_2 d} \right).$$↵
↵
So far, so good. I wrote Python code (with `double` representation), and failed. Rewrote in C++ using `long double`, and succeeded. But..., what was wrong?↵
↵
↵
### Loss of significance↵
The culprit is [loss of significance (wikipedia)](https://en.wikipedia.org/wiki/Loss_of_significance). It occurs when you take difference $(y - x)$ of two close numbers $x \approx y$. For example, ↵
↵
$$1.0023 - 1.0019 = 0.0004$$ ↵
↵
The difference has only one significant digit although you started with numbers of five significant digits!↵
↵
↵
This type of numerical error can happen in two parts. One in inside of $\arccos()$, the other in the function $(\theta - \sin\theta \cos \theta )$ when $\theta$ is small $\theta \ll 1$.↵
↵
Inside of the $\arccos$ is just arithmetic operations so we can represent numbers asf`Fractions` to avoid the error. ($d$ is a floating point number but I still convert it into a fraction as well.)↵
↵
$(\theta - \sin\theta \cos \theta )$ involves non-arithmetic operation, so I use [Taylor expansion](https://en.wikipedia.org/wiki/Taylor_series). Wolfram|Alpha [tells](http://www.wolframalpha.com/input/?i=lim+%28x+-+sin+x+cos+x%29+as+x-%3E0) me like this.↵
↵
$$ f(x) = x - \sin x \cos x = \frac{2}{3} x^3 - \frac{2}{15} x^5 + \frac{4}{315} x^7 + O(x^9) $$↵
↵
The first three termsisare good enough. I replaced the function $f(x)$ with this form when $\lvert x \rvert| < 0.001$.↵
↵
↵
### Am I wrong, or test is wrong?↵
↵
Here is my Python implementation. ↵
↵
```python↵
"""↵
Codeforces Educational Round 2↵
↵
Problem 600 D. Area of Two Circles' Intersection↵
↵
@author yamaton↵
@date 2015-11-30↵
2015-12-02↵
"""↵
import math↵
import fractions↵
↵
↵
def f(x):↵
"""↵
compute x - sin(x) cos(x) ↵
without loss of significance↵
"""↵
cos = math.cos↵
sin = math.sin↵
↵
if abs(x) < 0.001:↵
return 2 * x**3 / 3 - 2 * x**5 / 15 + 4 * x**7 / 315↵
return x - sin(x) * cos(x)↵
↵
↵
def solve(r1, r2, d):↵
acos = math.acos↵
↵
r1, r2 = min(r1, r2), max(r1, r2)↵
if d >= r1 + r2: # circles are far apart↵
return 0.0 ↵
if r2 >= d + r1: # whole circle is contained in the other↵
return math.pi * r1 ** 2↵
↵
# Convert numbers into fractions before calculation.↵
# Numbers are fractions until `acos()` is applied.↵
r1f, r2f, df = map(fractions.Fraction, [r1, r2, d])↵
r1sq, r2sq, dsq = map(lambda i: i * i, [r1f, r2f, df])↵
theta1 = acos((r1sq + dsq - r2sq) / (2 * r1f * df))↵
theta2 = acos((r2sq + dsq - r1sq) / (2 * r2f * df))↵
↵
return r1 * r1 * f(theta1) + r2 * r2 * f(theta2)↵
↵
↵
def main():↵
x1, y1, r1 = map(int, input().split())↵
x2, y2, r2 = map(int, input().split())↵
d = math.hypot(x1-x2, y1-y2)↵
result = solve(r1, r2, d)↵
print("%.20f" % result)↵
↵
↵
if __name__ == '__main__':↵
main()↵
```↵
↵
But this **STILL** fails on test 36. Here is a screenshot.↵
↵
↵
↵
Am I wrong? Or, the test is wrong?↵
[problem:600D] requires careful treatment of loss of significance, more than the geometry itself. The test is plagued by the numerical errors, and rejects "more accurate" solution.↵
↵
↵
### Geometry ↵
Let's review the geometry, first. We need three numbers $(r_1, r_2, d)$; where $d$ is the distance between two centers,↵
↵
$$ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}. $$↵
↵
When two circles do not intersect, which is the case $d > r_1 + r_2$, the area of intersection is zero.↵
↵
When one circle is contained in the other, which is the case $\max(r_1, r_2) >= d + \min(r_1, r_2)$, the intersection equals to the smaller circle.↵
↵
↵
↵
Otherwise, intersection of two circles is determined from two circular sectors subtracted by two triangles, yielding↵
↵
$$ \mathrm{Intersection} = r_1^2 ( \theta_1 - \sin \theta_1 \cos \theta_1) + r_2^2 ( \theta_2 - \sin \theta_2 \cos \theta_2). $$↵
↵
where angles $\theta_1$ and $\theta_2$ are determined from the cosine formula↵
↵
$$\theta_1 = \cos^{-1} \left( \frac{r_1^2 + d^2 - r_2^2}{2 r_1 d} \right),$$↵
↵
$$\theta_2 = \cos^{-1} \left( \frac{r_2^2 + d^2 - r_1^2}{2 r_2 d} \right).$$↵
↵
So far, so good. I wrote Python code (with `double` representation), and failed. Rewrote in C++ using `long double`, and succeeded. But..., what was wrong?↵
↵
↵
### Loss of significance↵
The culprit is [loss of significance (wikipedia)](https://en.wikipedia.org/wiki/Loss_of_significance). It occurs when you take difference $(y - x)$ of two close numbers $x \approx y$. For example, ↵
↵
$$1.0023 - 1.0019 = 0.0004$$ ↵
↵
The difference has only one significant digit although you started with numbers of five significant digits!↵
↵
↵
This type of numerical error can happen in two parts. One in inside of $\arccos()$, the other in the function $(\theta - \sin\theta \cos \theta )$ when $\theta$ is small $\theta \ll 1$.↵
↵
Inside of the $\arccos$ is just arithmetic operations so we can represent numbers as
↵
$(\theta - \sin\theta \cos \theta )$ involves non-arithmetic operation, so I use [Taylor expansion](https://en.wikipedia.org/wiki/Taylor_series). Wolfram|Alpha [tells](http://www.wolframalpha.com/input/?i=lim+%28x+-+sin+x+cos+x%29+as+x-%3E0) me like this.↵
↵
$$ f(x) = x - \sin x \cos x = \frac{2}{3} x^3 - \frac{2}{15} x^5 + \frac{4}{315} x^7 + O(x^9) $$↵
↵
The first three terms
↵
↵
### Am I wrong, or test is wrong?↵
↵
Here is my Python implementation. ↵
↵
```python↵
"""↵
Codeforces Educational Round 2↵
↵
Problem 600 D. Area of Two Circles' Intersection↵
↵
@author yamaton↵
@date 2015-11-30↵
2015-12-02↵
"""↵
import math↵
import fractions↵
↵
↵
def f(x):↵
"""↵
compute x - sin(x) cos(x) ↵
without loss of significance↵
"""↵
cos = math.cos↵
sin = math.sin↵
↵
if abs(x) < 0.001:↵
return 2 * x**3 / 3 - 2 * x**5 / 15 + 4 * x**7 / 315↵
return x - sin(x) * cos(x)↵
↵
↵
def solve(r1, r2, d):↵
acos = math.acos↵
↵
r1, r2 = min(r1, r2), max(r1, r2)↵
if d >= r1 + r2: # circles are far apart↵
return 0.0 ↵
if r2 >= d + r1: # whole circle is contained in the other↵
return math.pi * r1 ** 2↵
↵
# Convert numbers into fractions before calculation.↵
# Numbers are fractions until `acos()` is applied.↵
r1f, r2f, df = map(fractions.Fraction, [r1, r2, d])↵
r1sq, r2sq, dsq = map(lambda i: i * i, [r1f, r2f, df])↵
theta1 = acos((r1sq + dsq - r2sq) / (2 * r1f * df))↵
theta2 = acos((r2sq + dsq - r1sq) / (2 * r2f * df))↵
↵
return r1 * r1 * f(theta1) + r2 * r2 * f(theta2)↵
↵
↵
def main():↵
x1, y1, r1 = map(int, input().split())↵
x2, y2, r2 = map(int, input().split())↵
d = math.hypot(x1-x2, y1-y2)↵
result = solve(r1, r2, d)↵
print("%.20f" % result)↵
↵
↵
if __name__ == '__main__':↵
main()↵
```↵
↵
But this **STILL** fails on test 36. Here is a screenshot.↵
↵
↵
↵
Am I wrong? Or, the test is wrong?↵
