class ClosestPair
end
class << ClosestPair
  private
  def distance(p0,p1)
    a,b = p0[0]-p1[0], p0[1]-p1[1]
    dd = a*a+b*b
    Math.sqrt(dd)
  end
  def calc_index(d,p)
    [((2*p[0])/d).floor, ((2*p[1])/d).floor]
  end
  def calc_0(data)
    if data.length < 2
      raise "invalid input"
    end
    p0 = data[0]
    p1 = data[1]
    d = distance(p0,p1)
    pair = [0,1]
    h = {}
    h[calc_index(d,p0)] = 0
    h[calc_index(d,p1)] = 1
    cur = 2
    while cur < data.length
      idx = calc_index(d,data[cur])
      min = 2.0
      min_i = nil
      (-2..2).each do |y|
        (-2..2).each do |x|
          qi = h[[idx[0]+x, idx[1]+y]]
          next unless qi
          td = distance(data[cur],data[qi])
          if td < min
            min = td
            min_i = qi
          end
        end
      end
      if min_i && (min < d)
        pair = [cur, min_i]
        d = min
        h = {}
        (0..cur).each do |i|
          h[calc_index(d,data[i])] = i
        end
      else
        h[idx] = cur
      end
      cur += 1
    end
    pair
  end
  public
  def calc(data)
    calc_0(data.shuffle)
  end
end

if __FILE__ == $0
  def time(mes, &blk)
    start_time = Time.now
    blk.call
    puts "%s : %.2f sec." % [mes, Time.now-start_time]
  end
  data = []
  n = 10000
  n.times do
    data << [Random.rand, Random.rand]
  end
  time "Randomized Closest Pair(#{n} items)" do
    ClosestPair::calc(data)
  end
end