@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…”
@migdal You have this stuff:
counter++;
if(counter>100)return 0;
Note that test file could have up to 1000 test cases.
@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
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?
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.
1 Like
@anton_lunyov :
hi, I also suffered during contest. And I test my program with your data given above,
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
I think this data is same as(since the other two are totally inside)
965 290 2
933.21 379.95 597.64
534.57 978.93 816.87
and I draw them using software. And then I find the answer should be more than 100 ?!
Is there anything wrong? Can you help me?
@vineetpaliwal @ftiasch Sorry guys, I’ve extracted that test incorrectly. The correct one is:
768 13 4
0.03 12.84 767.97
0.01 12.98 767.99
768.00 780.97 768.00
0.05 12.98 318.07
The answer as above: 12.9705983.
Now I visualize it as well. It is very corner case where you can’t even use picture to see the answer
We have two very close circles here which look the same on the picture.
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.
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
… I have written down some note about me solving this problem during the contest … (Written in Chinese)
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.
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&