Circles intersection problem [Help]

Revision en1, by himanshujaju, 2016-04-09 19:18:09

Recently in a contest I came across this question :

"Given N circles, defined by their x co-ordinate, y co-ordinate and radius, remove the minimum number of circles such that the remaining circles are non intersecting. Touching a circle is also considered as intersecting."

Constraints 1 <= N <= 1000 0 <= abs(X) , abs(Y) , abs(R) <= 1000

The setter solution uses a greedy solution (to remove the circle with maximum intersections everytime till all remaining are non intersecting), but this fails on a very simple test case.

Here, the greedy solution gives answer as 4, but we can do it by removing 3 circles also.

Tags help, geometry, np

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English himanshujaju 2016-04-09 19:25:30 0 (published)
en2 English himanshujaju 2016-04-09 19:24:51 348 Tiny change: 'straints\n1
en1 English himanshujaju 2016-04-09 19:18:09 763 Initial revision (saved to drafts)