×

ANDOOR - Editorial

Author: Vitalij Kozhukhivskij
Tester: Anton Lunyov
Editorialist: Anton Lunyov

MEDIUM

PREREQUISITES:

Computational Geometry: Circle-Cirle Intersection, Line-Circle 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 non-trivial 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 well-known 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 half-plane 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 sweep-line 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 :)

1. General tip: always try to avoid floating point computations. In this problem the main pitfall is that points are given as floating values and most of the contestants deal with them as they are. But the only safe way to deal with the input values is to multiply them by 100 and round them (rounding is important) and then deal only with integers values except some places where we can't avoid floating point arithmetic. Hence if you have WA and do not use this suggestion any complains will be rejected :)

2. Now I describe the most evil bug that could be in this problem, when you are not using integer values and do some unsafe check. Assume that you are checking whether the circle intersects with the right side of the rectangle. If the parameters of the current circle are (X, Y, R) then your check could look like:
if (fabs(W - X) < R) do arc erase
Due to floating point issues this check could sometimes work when circle is tangent to this line. For example when R = 0.1, W = 1 and X = 0.9 this indeed happens. AFAIK some contestants contrived to avoid this by switching to long double type (they even got AC after this). IMHO it is some kind of tambourine dance (it is idiom in Russian :)). At least such switch is compiler depended because at some compilers double = long double.
But we move on. So in the case of equal numbers from our point of view they somehow stored in double as non-equal numbers. So in our example we have
0.1 = 0.10000000000000001
and
1 − 0.9 = 0.099999999999999978.
The difference is just about 2e-17. As mentioned above we consider this circle as intersecting with the side of the rectangle and add some arc to the list of arcs. Namely the arc [-A, A] will be added in this case, where
A = acos((W − X) / R).
"So what?" you think probably now: the negligible intersection should add negligible arc. Like hell it will! Just calculate acos((1 − 0.9) / 0.1). It is about 2.1e-8, which is quite far from negligible. To understand this we should involve some properties of inverse cosine function. Namely, acos(1 − x) = sqrt(2 * x) * (1 + o(1)), when x tends to zero (it has very simple geometric proof). Hence when x was just around 1e-17 the acos(1 − x) is not very small. To ensure that this indeed may lead to a bug check it out this example. As wee see the circle is tangent to the side of the rectangle but due to the incorrect comparison we cut some considerable part from the circle that leads to absolute error of about 2.8e-5 in the output, which is 28 times larger than allowed error 1e-6. (The code assume that the door is the half-plane :-[, but it should work in general case too).

3. The same bug could also occur when we try to intersect tangent circles. It is geometrically clear that very small difference between distance and sum of radii could lead to considerable arcs cut from the circles. Hence you should either use comparison using integers to check tangent circles properly or use wise epsilon if you still want to use doubles.

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.
Tester's solution can be found here.

RELATED PROBLEMS:

This question is marked "community wiki".

6.7k62119138
accept rate: 12%

1

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

(16 Jan '13, 10:43) 5★

 4 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 1.1k●4●9●17 accept rate: 0% 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 4-5 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) kuruma3★ I think that precision problems are a fair game in a 10-day 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) thocevar6★ 2 Actually, he exactly traps in the situation explained in the paragraph 2. Note that he performs the intersection check with right side as if (circ[i][0]+circ[i][2]>W) { where circ[i][0] and circ[i][2] are doubles. While he uses integers testcirc[i][j] only for some intermediate checks. 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 thought-out 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 And actually the style of that your answer was a bit offensive for me. (16 Jan '13, 09:39) showing 5 of 7 show all
 3 My reply to triplem. In short, the reason is that when we have the intersection, then acos() is calculated for numbers not very close to the critical points 1 and -1 and hence effects above are not so huge. When we calculate acos((W-X)/R) and similar 3 others, the argument is at least 1e-5 away of critical points and the error of 1e-17 for number of the form x = 1 − 1e-5 leads to error about 2e-15 in acos(x). Which IMHO is safe. But when we calculate intersection of circles situation is much more interesting. Even for the test I posted above: 1000 1000 2 10.00 10.00 0.02 674.94 756.87 1000.00  We need to calculate acos of the number like 1 − 1e-15 here: double alp = acos((sqr(Ri) + Dij - sqr(Rj)) / (2 * Ri * sqrt(double(Dij)))); The error of 1e-17 for number of the form x = 1 − 1e-15 leads to error about 2e-10 in acos(x). Which could be too large error. But in this test case we need the answer with relative error 1e-9 so this formula produces the correct result. I have came up with another solution where I can guarantee the precision near 1e-13 of the answer for every possible test case and verify that our answers are correct. This is some combination of weakness of test data and luckiness at some critical test data :) So I can guarantee that each AC solution produces the correct answer for official test data. But they are weak and probably it is possible to create a set of test data where all solutions including author's and tester's ones will produce incorrect result. My new solution is quite tricky. So it is very sad for me that I did not have enough time to investigate all this before the contest. I see now that with having 5-6 digits after the decimal in initial points and asking for absolute or relative error of 10-12 this could be really HARD problem from precision issues perspective though quite straightforward at the first sight. I don't want to disclose my new solution, since I have a wish to post some similar problem in near future, though I am afraid that this problem has already revealed too many tricks. P.S. Also forget to mention that the number of arcs in the answer unlikely could be close to a million. Note that exactly this value affects on the resulting precision since the answer is the sum of length of all separate arcs on each circle. We have this maximum near 5000 in our test data. And I have no idea what is the real maximum. Also I don't know exactly what could be the maximal possible answer under the given constraints. My guess is something like O(W * sqrt(N)). The example for this value is non-intersecting circles arranged like in the square grid. We have such test in the system. The answer of it is near 99000. And actually many of you have WA on it due to acos() trick described in the editorial. So there are many open problems here left if someone want to design the toughest possible test data. answered 16 Jan '13, 09:23 6.7k●62●119●138 accept rate: 12% 3 Thanks. And sorry again about the initial response; having spent quite a while debugging precision issues I got a bit frustrated finding that they weren't actually completely intended / accounted for in the official solution either (hopefully you can understand that!). But I'm not surprised you hadn't found them either - there's a lot more complexity to this than I was thinking. (16 Jan '13, 09:37)
 2 although i have spent quite a few days on this problem, even hated it, but finally when i have solved it, i almost liked it. i have learned a few things about floating point precision and that's my gain on this problem. answered 15 Jan '13, 22:49 194●1●1●5 accept rate: 0% 2 Thanks. It's like a balm to the soul :) Actually we did not expect any such precision issues with this problem. I was quite busy with other problems so forgot to consider this problem carefully from this perspective. I've only noticed that we ask for 1e-11 relative error in the worst case. Since working double precision is 1e-16 I was absolutely sure that all will be fine. The acos() trick was noticed only in the middle of the contest. Actually I did some additional investigation. So you could expect some evilest problem ever on precision from me in the near future ;) (15 Jan '13, 23:01)
 1 I'm still not clear on why either of the provided solutions are correct. You have shown in the editorial that if the intersection between two circles is actually 0, then using doubles for comparisons can result in a WA because tiny errors in doubles can cause a tiny error in the size of the intersection, but enough to cause a WA. Consider two circles which do intersect. You have no choice but to use doubles, and tiny errors in doubles will cause a tiny error in the length of the intersection. Unless I'm mistaken, there could be just over 2 million intersections all which contribute to the final sum, so each intersection needs to be calculated to better than 10^-12 accuracy. Can you prove that both provided solutions do this? Trig functions will quickly escalate any errors, as you also noted. Feel free to correct my logic if this is not true. answered 16 Jan '13, 01:21 1.1k●4●9●17 accept rate: 0% I think you cannot prove that these solution are 100% correct, but one may reason as follows to "show" that a big error is unlikely to occur: each precision error can be seen as a random value say in interval (-eps,eps) if we sum n such values: by CLT, the probability that we get an error bigger than 3epssqrt(n) is negligible. (16 Jan '13, 01:38) damians6★ Ah, and the edge cases only make a difference due to the fact you don't get the negatives cancelling them out. Still, with n being a million, and the fact that you have to raise the probability of success to the power of 1000 test cases.. (16 Jan '13, 01:45)
 0 Hi Anton, at the contest page you promised you'd provide me (after the contest) with the only test case where my AC submission differs from my "best WA" submission. How do I get it? Thanks! answered 15 Jan '13, 19:46 1●1 accept rate: 0% 1000 1000 2 10.00 10.00 0.02 674.94 756.87 1000.00 Our answer is 28.5976846 While your answer is 28.5976824 (15 Jan '13, 21:26) Thanks a lot! Turns out I was very lucky with my AC submission. In fact, my AC submission has more rounding errors, but they pull in opposite directions :-) (15 Jan '13, 23:20)
 0 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 2.2k●7●26●33 accept rate: 20% Try this: 628 184 2 477.64 0.00 0.03 172.00 0.01 305.62 If I count correctly till 15 then this should be your test :) Correct answer is 197.4966989 while your answer is 197.497702703. (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)
 0 @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 3★dirayet 1 accept rate: 0% @dirayet Your program produces negative answer for the following test: 839 674 2 838.98 437.29 839.02 430.11 574.67 530.12 If I correctly extracted the 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) dirayet3★
 0 @anton_lunyov : Please tell a test case for Submission ID : 1721687 answered 16 Jan '13, 19:24 627●1●7●13 accept rate: 27% @javadecoder You should either use integers for circle parameters or do check of intersection of circle with side using epsilon. You exactly trap in the situation described in the editorial. (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)
 0 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 1●1 accept rate: 0% We definitely have such tests or more trickier ones. In your example we add two overlapping arcs to the list of arcs. Then we sort arcs by their ends and find their union. Finally we subtract the length of this union from the circle length. 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)
 0 ... 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 5★xiaodao 196●3●5 accept rate: 0% 1 The test where the answer is wrong is: 289 615 2 907.66 6.65 978.67 571.01 364.42 244.03 The answer is zero while yours one is 79.6440876. 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) xiaodao5★ 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/codechef-january-challenge-2013/ 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) xiaodao5★ 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) xiaodao5★
 -1 Turns out using (22.0/7.0) gives a different pie value than acos(-1) , causing the precision problem for my solution. Shouldnt 22.0/7.0 be more accurate ? answered 16 Jan '13, 01:16 0●2●4●5 accept rate: 0% 1 so just googled it, and 22/7 is actually the least accurate fraction for PIE. Huge lesson learned here. Great question all together! Lots to learn. Geometry + Programming is one of my weak points. (16 Jan '13, 01:22)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,657
×647
×27
×19
×1

question asked: 15 Jan '13, 15:00

question was seen: 8,198 times

last updated: 24 Jan '13, 06:07