Is the test of "Area of Two Circles' Intersection" correct?

Revision en10, by yamaton, 2015-12-03 00:03:52

TL;DR

600D - Area of Two Circles' Intersection 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 (r1, r2, d); where d is the distance between two centers,

Intersection of two circles is determined from two circular sectors subtracted by two triangles, yielding

where angles θ1 and θ2 are determined from the cosine formula

So far, so good. I wrote Python code (with double representation), and failed. Rewrote the code in C++ using long double, and succeeded. But..., what was wrong?

Loss of significance

Loss of significance (wikipedia) occurs when you take difference (y - x) of two close numbers x ≈ y. This can happen in two parts in our calculation. One in inside of cos - 1(), the other in the function (θ - sin{θ}cos{θ}) when x is small .

Tags errors, geometry, test, python

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en28 English yamaton 2015-12-05 17:51:41 30
en27 English yamaton 2015-12-05 17:44:25 2 Tiny change: '. (**EDIT2:** I was wro' -
en26 English yamaton 2015-12-05 17:42:43 93
en25 English yamaton 2015-12-05 17:39:25 11
en24 English yamaton 2015-12-05 17:37:30 20 Tiny change: 'icient in computing `acos`.\n\n2. `a' -> 'icient in significance.\n\n2. `a'
en23 English yamaton 2015-12-05 17:36:34 24 Tiny change: 'lly got AC: [submiss' -> 'lly got AC with `double` precision: [submiss'
en22 English yamaton 2015-12-05 17:35:44 1176 Tiny change: '21].\n\n** Lesson Learned: **\n\n- Ju' -
en21 English yamaton 2015-12-03 03:18:13 12 Tiny change: 'imgur.com/ObIOka0.png)\n\nO' -> 'imgur.com/NrqhykS.png)\n\nO'
en20 English yamaton 2015-12-03 03:00:55 391 Edited and modified
en19 English yamaton 2015-12-03 01:06:00 10 Fixed typos
en18 English yamaton 2015-12-03 00:52:35 0 (published)
en17 English yamaton 2015-12-03 00:49:27 24 Tiny change: 'n test 36.\n![ ](htt' -> 'n test 36. Here is a screenshot.\n\n![ ](htt'
en16 English yamaton 2015-12-03 00:47:48 1594
en15 English yamaton 2015-12-03 00:31:43 302
en14 English yamaton 2015-12-03 00:24:19 826
en13 English yamaton 2015-12-03 00:10:46 51
en12 English yamaton 2015-12-03 00:10:08 220
en11 English yamaton 2015-12-03 00:05:29 28
en10 English yamaton 2015-12-03 00:03:52 99
en9 English yamaton 2015-12-03 00:01:11 131
en8 English yamaton 2015-12-02 23:56:18 538
en7 English yamaton 2015-12-02 23:40:10 8 Tiny change: ' geometry problem itself.\n' -> ' geometry itself.\n'
en6 English yamaton 2015-12-02 23:39:47 150
en5 English yamaton 2015-12-02 23:33:39 27
en4 English yamaton 2015-12-02 23:32:04 283
en3 English yamaton 2015-12-02 23:29:53 15
en2 English yamaton 2015-12-02 23:28:55 476
en1 English yamaton 2015-12-02 23:24:53 858 Initial revision (saved to drafts)