Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

「キュラゲの最小包含円を求めよう」を解いてみました

CodeIQの「【計算幾何学】キュラゲの最小包含円を求めよう」を解いてみました。

solv.rb

# -*- coding: utf-8 -*-
CONVRGV = 1.0e-9
LOOPMAX = 100

def solvcircle(pt_x, pt_y)
  mvrate, maxdist = 0.5, 0.0
  xsv, ysv = 0.0, 0.0
  cx, cy = 0.0, 0.0
  cvgflg   = false
  while cvgflg == false
    LOOPMAX.times {|t|
      maxdist = 0.0
      k = nil
      pt_x.each_index {|i|
        dist = distance(cx, cy, pt_x[i], pt_y[i])
        if (dist > maxdist)
          maxdist = dist
          k = i
        end
      }
      cx += (pt_x[k] - xsv) * mvrate
      cy += (pt_y[k] - ysv) * mvrate
      if (distance(cx, cy, xsv, ysv) <= CONVRGV)
        cx = xsv
        cy = ysv
        cvgflg = true
        break
      end
      xsv = cx
      ysv = cy
    }
    mvrate /= 2.0
  end
  [cx, cy, maxdist]
end

def distance(x1, y1, x2, y2)
  Math.sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1))
end

xdata, ydata = [], []
File.open("points.csv") {|f|
  f.each_line {|line|
    x, y = line.split(",")[0, 2].map(&:to_f)
    xdata << x
    ydata << y
  }
}

puts "%f, %f, %f\n" % solvcircle(xdata, ydata)