@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
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.
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?
… 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
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.
@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&