Блог пользователя chill21

Minimum radius of the circle to cover atleast m points ?
Автор chill21, история, 8 лет назад, По-английски

Given N points in the 2- D plane , find minimum radius of the circle which encloses atleast m points?

thanks in advance

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

What is an algorithm for enclosing the maximum number of points in a 2-D plane with a fixed-radius circle? This can be solved in n*n*logn (see here)

Now to solve your problem all you need to do is to binary search over possible range of R to find the minimum R which encloses at least m points.

This problem was asked in recent codechef long challenge (click)

→ Ответить