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

Smallest circle set points [Help]

Автор Nuu, 7 лет назад, По-английски

Hi guys, i'm trying solve this problem.

The resume is: given a set of points, print the smallest circle that cover all points.

I'm searching, but only find aproximate algorithms.

Somebody know a algoritm without aproximate?

Thanks for advice.

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

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

Hi, I believe that this can help you out. :D

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    this approach gets WA because fail in coordinates approximation :/

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

Exact algorithms are described in Smallest-circle problem.

Best wishes

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

On a side note see this problem too . A slightly modified version of smallest enclosing circle : https://www.codechef.com/problems/CHEFCIRC

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can use nested ternary search though it is O(nlogC^2)

→ Ответить