PROBLEM LINK:Author: Vitalij Kozhukhivskij DIFFICULTY:MEDIUM PREREQUISITES:Computational Geometry: CircleCirle Intersection, LineCircle Intersection PROBLEM:You have completely black coordinate 2D plane. Then you color at white the region enclosed by the rectangle with the vertexes at the points (0, 0), (W, 0), (0, H), (W, H). Then for several circles you color at black the regions enclosed by each of the circle. You need to find the perimeter of the remaining white figure, but only that part of the perimeter that lies strictly inside the original rectangle. If someone is confused by this formulation here is another one that actually almost reveals the whole solution. For each circle you need to find the length of its boundary inside the rectangle that not covered by other circles and output the sum of these values over all circles. QUICK EXPLANATION:For each circle we will erase from its boundary several arcs covered by other circles or by outer part of the rectangle. But at first we should consider trivial corner cases: the circle lies completely outside the rectangle or the circle is completely covered by some other circle. In this case we skip this circle. I predict that many contestants actually have missed one of these cases. Now assume that circle is nontrivial and denote it by C. We will work with arcs as with polar angle segments. So initially we have one segment (Pi, Pi], where Pi = 3.1415926... is wellknown constant. Then for each other circle C' we at first check whether it intersects with C. If no, we move on (note that we already check that C is not covered completely by any other circle). Otherwise we find the intersection points of C and C' and add the corresponding arc on C to the list of arcs that should be erased. When all circles are processed we consider sides of the rectangle. For the given side we should find the part of C that lies in the outer halfplane corresponding to this side and add the corresponding arc to the list. When adding arcs, note that some arcs could cover the cut point Pi, in this case you should add two arcs to the list. When the list of arcs to erase is ready we sort corresponding segments of angles and use standard algorithm (some kind of sweepline algorithm) to find their union. Then the answer for the current circle is R * (2 * Pi − L), where R is its radius and L is a union of erased arcs. PRECISION ISSUES:I feel like we will have many complains due to this. But let me try to prevent most of them :)
EXPLANATION:Details will be provided soon. As of now refer to tester's solution. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:SPOJ  3863. Area of circles  VCIRCLES
This question is marked "community wiki".
asked 15 Jan '13, 15:00

And that is exactly why you will absolutely never find any quality contest problem solely asking for absolute error instead of an absolute/relative combination. answered 15 Jan '13, 15:13
5
IMHO this issue with acos() fair to be a trick of the high quality problem. If you are so smart then suggest some "quality contest problem" having some precision stuff. I am sick of your unfair critic comments! Really!
(15 Jan '13, 15:22)
10
Hey guys , don't fight ! I made 100 wrong submissions and am still laughing and maybe I will learn a few things after reading this editorial . I am still to figure out my mistake . Last two days of the contest I solved 45 easy problems from easy section of practice section to uplift my mood after my terrible time loss / energy loss and no points gained in this problem . Cheers , keep the energy positive :)
(15 Jan '13, 17:20)
^I agree with this completely!!! We are here to learn new things and enjoy problems, not fight with eachother! :)) Also, this community works hard as nobody other does and the problems are BETTER than some found at CGJ imho... So, let's just enjoy this
(15 Jan '13, 18:11)
I think that precision problems are a fair game in a 10day contest with an unlimited number of attempts. Actually, they deserve a place here. However, I'm still not sure where triplem's last WA submission failed. Long doubles saved the day in the end, but his solution seems to handle all the mentioned precision issues correctly.
(15 Jan '13, 18:11)
2
Actually, he exactly traps in the situation explained in the paragraph 2. This is one of reasons why I angry with him: I exactly explained in the editorial his bug but he still consider this problem as crappy precision problem. BTW I still didn't forget his comments for MAXCIR and CLOSEST.
(15 Jan '13, 21:22)
1
I apologise for the above post; it wasn't called for. (Though I'm not sure what you mean regarding MAXCIR/CLOSEST, in MAXCIR I mentioned an issue with unsigned integers that you/everyone else seemed to agree with, rather than any complaining?) My more thoughtout response is below.
(16 Jan '13, 01:33)
Well, I only wrote that I agree but I still believe that it is nice trick :P
(16 Jan '13, 09:39)
showing 5 of 7
show all

@admin please give the test cases for this problem as soon as possible . it will be of great help. answered 15 Jan '13, 19:16
Please provide ID of the submit for which you want to know the test. You last submits contains some weird checks.
(16 Jan '13, 15:06)
@anton_lunyov : I also need test cases for Submission ID : 1710810
(16 Jan '13, 15:17)
@vineetpaliwal
(16 Jan '13, 15:28)
Can you give me testcase where code with submission id 1725756 fails ? There is only one line difference between 1725756 and 1725755 , which does not fall in any of the possible mistakes you explained in the editorial . In this case error would because of difference between x and sqrt(x)*sqrt(x) . I am not able to understand this because I am using sqrt(x) in correct submission also .
(16 Jan '13, 18:04)
2
The output here is truncated. So I can't find any particular test case. Hence, I've run you program against the test where you have WA on ideone.com: It returns nan or some very large number for some tests. And now you can download that test case and play with it locally. Enjoy :)
(16 Jan '13, 18:56)
@admin for 1723008
(16 Jan '13, 19:31)
@migdal You have this stuff:
(17 Jan '13, 11:14)
@anton it was only for checking how many test caes my submission passed on the judge thanks for pointing it out i just forgot to remove it sorry for trouble :)
(17 Jan '13, 12:39)
@anton_lunyov :
hi, I also suffered during contest. And I test my program with your data given above,
(22 Jan '13, 18:06)
@vineetpaliwal @ftiasch Sorry guys, I've extracted that test incorrectly. The correct one is:
(22 Jan '13, 21:50)
showing 5 of 10
show all

Ahhh! 125 submissions and no AC (Failed after passing 7 test files). Yet to know my mistake. Could you help me @anton_lunyov . P.S:Code Ok with Test case given above. Thanks! answered 16 Jan '13, 01:03
Try this:
(16 Jan '13, 15:00)
@anton_lunyov : My code works fine with two test cases posted here . Can you give a test case specific to where my code fails . Thanks in advance .
(16 Jan '13, 15:03)
@anton_lunyov : Thanks for the test case :) I will have to find my mistake yet!
(16 Jan '13, 16:24)

@anton_lunyov, I'd really appreciate seeing the test data at which my code didn't match. I really need to know what was wrong. Thanks! P.S. Generated more than 20 challenging cases. My results including above match successful submissions. answered 16 Jan '13, 02:08
@dirayet Your program produces negative answer for the following test:
(16 Jan '13, 15:14)
@anton_lunyov, thank you very much. You are right! good job finding such test points; I learned a lot from this experience; "Never underestimate the problem, plan first to reveal all exceptions before the code grows..."
(17 Jan '13, 07:04)

@anton_lunyov : Please tell a test case for Submission ID : 1721687 answered 16 Jan '13, 19:24
@javadecoder
(17 Jan '13, 01:06)
1
@anton_lunyov : Actually I had tried taking long long before and still I was getting wrong answer . But I just checked that it got AC only on adding 0.01 to it((LL)(r*100+0.01)), and then converting into long long , which appears really strange to me as how could that make a difference . Be it bad luck or something else, but I am really disappointed that just adding 0.01 makes my WA to AC , and I missed it in the contest.
(17 Jan '13, 01:56)
2
@javadecoder It is completely correct behavior. Floats are stored in binary by compiler and if number has infinite expansion into binary fraction then it is truncated somehow. For example, 0.1 has binary form 0.000110011001100... So it is not exact value. That is why when r = 1.01 then 100*r could equal to 100.999999999999 and will be considered as 100 when converted to long long instead of 101. I learned this almost 6 years ago :)
(17 Jan '13, 02:34)

Is there not any test case where three or more circle intersect with each other like http://www.daviddarling.info/images/Venn_diagram.gif As in this case if we we find the intersection points of C and C' and add the corresponding arc on C to the list of arcs that should be erased then some part of the arc will remove two or more times. answered 17 Jan '13, 17:51
We definitely have such tests or more trickier ones. In your example we add two overlapping arcs to the list of arcs. So if for example you add two overlapping arcs [1, 2.5] and [1.5, 3] to the list, then their union is just one arc [1, 3]. So you subtract 3  1 = 2 from the answer and not 2.5  1 and then 3  1.5. Is this clear your doubt?
(17 Jan '13, 18:57)

... Hi, eventually I find my bug with my code during the contest ... .. I only delete a segment of code about the circle outside the rectangle ... But still, I can not figure out .. why my previous method was wrong .... ... Is there any guy who can help me find that ? ... THanks A Lot ! .. lol !!... Correct: http://www.codechef.com/viewsolution/1744236 Wrong ( But didn't know the reason ... http://www.codechef.com/viewsolution/1744238 answered 22 Jan '13, 08:12
1
The test where the answer is wrong is: It seems that the first circle covers rectangle completely and the second one lies completely outside the rectangle. But I don't know why exactly the change you've made fixed the bug.
(22 Jan '13, 12:25)
Hi, I have found my silly bug ... :) now the two program return a same answer in my local test: neigher 0 or 79.644 but 281.3805175.
(23 Jan '13, 02:13)
Sorry. I've written incorrect answer. Actually your program with id 1744238 returns 0 here while the correct answer is 281.3805175. So it seems that you've resolved the issue :)
(23 Jan '13, 02:58)
.. I have written down some note about me solving this problem during the contest ... (Written in Chinese) http://www.shuizilong.com/house/archives/codechefjanuarychallenge2013/ I am not carefully enough so that although I found all the precision issues but still remain another small bug in my code, I have really learn a lot from this problem ... Thanks a lot for this problem and the strong data set, I am hoping there could be more Geometry Problem in the future.
(24 Jan '13, 06:05)
PS: I have also heard that "Voronoi diagram in Laguerre geometry" could solve this type problem in O(nlogn), but it is too diffuclut for me to grasp, any one here could implement it? http://epubs.siam.org/doi/abs/10.1137/0214006?journalCode=smjcat&
(24 Jan '13, 06:05)

... I have never seen such a detailed disccusion on precision issues before !..