Блог пользователя hongjun-7

Автор hongjun-7, история, 9 лет назад, По-английски
  1. Smallest Enclosing Circle : 2-Dimension Problem (Written in Korean. Output is the smallest enclosing circle's position on the first line and the radius on the second line.)

  2. Smallest Enclosing Sphere : 3-Dimension Problem

Thesis Link

Let P(X, Y, Z) = (Average(x(i)), Average(y(i)), Average(z(i)))

Average(x(i)) = Sum(x(i)) / N

Average(y(i)) = Sum(y(i)) / N

Average(z(i)) = Sum(z(i)) / N

P is inside of the points' convex hull.

Now find the farthest point(M) to P.

Move P toward M a little bit and the ratio should be small and decreasing.

If there is no such a movement, that is the answer.

Total Time Complexity is O(N * constant number)

(We can reduce 'N' by getting convex hull.)

My 2-Dimension Problem's Solution Code

My 3-Dimension Problem's Solution Code

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

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
»
8 лет назад, # |
  Проголосовать: нравится -45 Проголосовать: не нравится

Could you please explain the code for 2D ??

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