Nuu's blog

By Nuu, 5 years ago, In English

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.

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

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

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

    this approach gets WA because fail in coordinates approximation :/

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Exact algorithms are described in Smallest-circle problem.

Best wishes

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Could you explain your solution in detailed please ? thanks in advance.