Nuu's blog

By Nuu, 6 days 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  

»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

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

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

    this approach gets WA because fail in coordinates approximation :/

»
6 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Exact algorithms are described in Smallest-circle problem.

Best wishes

»
6 days 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

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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