newbeginBKB's blog

how to solve ZOJ 1450 Minimal Circle

By newbeginBKB, 11 years ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply