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
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 
2 Likes
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
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.
1 Like
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.
1 Like
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.
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…
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:
A8OB3T - Online C++ Compiler & Debugging Tool - 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 
2 Likes