@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.
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.
3 Likes
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.
3 Likes
Well, I only wrote that I agree but I still believe that it is nice trick 
And actually the style of that your answer was a bit offensive for me.
… I have never seen such a detailed disccusion on precision issues before !..
1 Like
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.
@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 .
Please provide ID of the submit for which you want to know the test. You last submits contains some weird checks.
@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.
@vineetpaliwal
965 290 4
978.17 335.00 44.97
933.21 379.95 597.64
896.96 980.24 362.36
534.57 978.93 816.87
The answer is 12.9705983
while your answer is 12.91059874336296
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 .
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:
http://ideone.com/A8OB3T
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
2 Likes
@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.
@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.
1 Like
@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
2 Likes
@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…”