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

how to solve ZOJ 1450 Minimal Circle

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

I think there will be at least two point on the convex hull. So first step I get the convex hull of given points. then run the O(n^3) algorithm but I get WA. Can you explain Why is it not correct?

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

»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

To get the right answer, it's necessary to check not only all pairs of points, but the triples too.

Upd. However, it's much easier to use gradient descend or ternary search.

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

    I think when the circle surround the convex hull then it must surround all the point ,so I transform the initial ploblem to get the miniman circle which can surround the convex hull

    I can get AC when run O(n^3) algorithm directly.

    But sorry,I dont'n know how to describe my algorithm.

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

I think there will be at least two point on the convex hull

You may cover only points from convex hull. If these points are covered, all points are covered. So mininimal circle touches two or three points from convex hull.

P.S. wiki

→ Ответить