https://www.codechef.com/viewsolution/20940954
i have pre-processed the min and max distance between each pair of cirlces and after that i have checked for each min and max that if given K lies between min and max then answer++ and in last printed answer.
Can anyone please help me to find out whats wrong in my approach.
I think you’re splitting your circles into cases wrong. Say you have circles with centers c_1,c_2 and radii r_1,r_2 (wlog assume that r_1 \ge r_2), then you want to split circles with into the cases
Completely disjoint, |c_1-c_2| > r_1+r_2
One circle inside the other, not disjoint and |c_1-c_2| < r_1 - r_2
Intersecting, not disjoint and not inside
All these cases have the same maximum distance d_\text{max} = r_1 + r_2 + |c_1-c_2| but different minimum distances
You can probably see why those distances are correct if you just draw the circles. If you don’t I could post some images.
When you have computed all [d_\text{min},d_\text{max}] intervals you can for the small case do the O(Q N^2) approach just by checking all intervals against the given d. To get the large case as well you need to be a bit more clever and use sorting and binary search to speed up things to time complexity O(N^2 \log{N} + Q \log{N}).
@hemant_dhanuka A big issue I see it that you’re using long to store your distances, the distances are not integers! You really should use double there. Your if statements are a bit hard to follow so there could be something wrong there too, but I’m not sure. Try to fix the distances first, if that doesn’t do it you probably have some issues in the circle logic.