読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

競技プログラミング

Golf関係でCodeIQのアカウントを取ったのだが、計算幾何学の問題があったのでちょっと解いてみた。
https://codeiq.jp/ace/stakemura/q296
フィードバックが返ってきてるので、ソースコード公開してもいいんだよね。
Computational Geometry: Algorithms and Applicationsを参考というかパクって実装。3点が同一直線上に乗る場合の処理を追加した。乱択アルゴリズム

127.5, 75.5,
の入力に対し、gets.split.map(&:to_f)でうまく動くのが新しい発見。

#!ruby2.0

class Point
  attr_reader :x,:y
  def initialize(x,y)
    @x,@y=x,y
  end

  #return square Euclidean distance
  def dist2(point)
    (@x-point.x)**2+(@y-point.y)**2
  end

  #return Euclidean distance
  def dist(point)
    dist2(point)**0.5
  end
end

class Circle
  EPS=1e-30
  def Circle.generate_from_2points(p1,p2)
    center=Point.new((p1.x+p2.x)/2,(p1.y+p2.y)/2)
    circle=Circle.new(center,center.dist(p1))
  end

  #we assume p1 is a boundary(edge) point,
  #i.e. circle have to pass on it whether p2,p3 does not.
  def Circle.generate_from_3points(p1,p2,p3)
    a=2*(p3.x-p2.x)
    b=2*(p3.y-p2.y)
    c=2*(p2.x-p1.x)
    d=2*(p2.y-p1.y)
    x=p3.x**2-p2.x**2+p3.y**2-p2.y**2
    y=p2.x**2-p1.x**2+p2.y**2-p1.y**2
    
    #solve the fol. linear eq.
    #(a b)(x0)=(x)
    #(c d)(y0) (y)
    
    det=a*d-b*c

    #in case 3 points lie on some line,
    #we ignore mid-point and generate circle from two edge points.
    #the mid-point must be p2 or p3
    if det.abs<EPS
      circle=Circle.generate_from_2points(p1,p2)
      circle=Circle.generate_from_2points(p1,p3) unless circle.contains?(p3)
    end

    center=Point.new((d*x-b*y)/det,(-c*x+a*y)/det)
    Circle.new(center,center.dist(p1))
  end

  def initialize(center,radius)
    @center,@radius=center,radius
  end

  def contains?(point)
    @center.dist2(point)<=@radius**2
  end

  def to_s
    "[x=%f, y=%f, r=%f]"%[@center.x,@center.y,@radius]
  end
end

class Points
  def initialize(points=[])
    @points=points
  end

  def <<(point)
    @points << point
  end

  #return the [center_point,radius], the smallest enclosing disk of @points
  #this is randomized algorithm and done in O(n) expected time
  def smallest_enclosing_disk
    pts=@points.shuffle
    
    raise RunTimeError if pts.size==0
    return Circle.new(pts.first,0.0) if pts.size==1
    return Circle.generate_from_2points(pts.first,pts.last) if pts.size==2
    
    def min_disk_with_2points(pts,q1,q2)
      circle=Circle.generate_from_2points(q1,q2)
      pts.each{|p|
          circle=Circle.generate_from_3points(p,q1,q2) unless circle.contains?(p)
      }
      circle
    end

    def min_disk_with_point(pts,q)
      circle=Circle.generate_from_2points(pts.first,q)
      1.upto(pts.size-1){|i|
        circle=min_disk_with_2points(pts[0..i-1],pts[i],q) unless circle.contains?(pts[i])
      }
      circle
    end

    def min_disk(pts)
      circle=Circle.generate_from_2points(pts[0],pts[1])
      2.upto(pts.size-1){|i|
        circle=min_disk_with_point(pts[0..i-1],pts[i]) unless circle.contains?(pts[i])
      }
      circle
    end

    min_disk(pts)
  end

  def sed_valid?(circle)
    @points.all?{|p|circle.contains?(p)}
  end
end

#retrive data from standard input, format is
#127.5, 75.5,
#ruby2.0 smallestEnclosingDisk.rb < points.csv
csv_points=[]
while line=gets
  csv_points << line.split.map(&:to_f)
end

csv_points.uniq!

points=Points.new
csv_points.each{|p|
  points << Point.new(*p)
}

sed=points.smallest_enclosing_disk
puts sed

#puts points.sed_valid?(sed)