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

Y2xhc3MgQ2xvc2VzdFBhaXIKZW5kCmNsYXNzIDw8IENsb3Nlc3RQYWlyCiAgcHJpdmF0ZQogIGRlZiBkaXN0YW5jZShwMCxwMSkKICAgIGEsYiA9IHAwWzBdLXAxWzBdLCBwMFsxXS1wMVsxXQogICAgZGQgPSBhKmErYipiCiAgICBNYXRoLnNxcnQoZGQpCiAgZW5kCiAgZGVmIGNhbGNfaW5kZXgoZCxwKQogICAgWygoMipwWzBdKS9kKS5mbG9vciwgKCgyKnBbMV0pL2QpLmZsb29yXQogIGVuZAogIGRlZiBjYWxjXzAoZGF0YSkKICAgIGlmIGRhdGEubGVuZ3RoIDwgMgogICAgICByYWlzZSAiaW52YWxpZCBpbnB1dCIKICAgIGVuZAogICAgcDAgPSBkYXRhWzBdCiAgICBwMSA9IGRhdGFbMV0KICAgIGQgPSBkaXN0YW5jZShwMCxwMSkKICAgIHBhaXIgPSBbMCwxXQogICAgaCA9IHt9CiAgICBoW2NhbGNfaW5kZXgoZCxwMCldID0gMAogICAgaFtjYWxjX2luZGV4KGQscDEpXSA9IDEKICAgIGN1ciA9IDIKICAgIHdoaWxlIGN1ciA8IGRhdGEubGVuZ3RoCiAgICAgIGlkeCA9IGNhbGNfaW5kZXgoZCxkYXRhW2N1cl0pCiAgICAgIG1pbiA9IDIuMAogICAgICBtaW5faSA9IG5pbAogICAgICAoLTIuLjIpLmVhY2ggZG8gfHl8CiAgICAgICAgKC0yLi4yKS5lYWNoIGRvIHx4fAogICAgICAgICAgcWkgPSBoW1tpZHhbMF0reCwgaWR4WzFdK3ldXQogICAgICAgICAgbmV4dCB1bmxlc3MgcWkKICAgICAgICAgIHRkID0gZGlzdGFuY2UoZGF0YVtjdXJdLGRhdGFbcWldKQogICAgICAgICAgaWYgdGQgPCBtaW4KICAgICAgICAgICAgbWluID0gdGQKICAgICAgICAgICAgbWluX2kgPSBxaQogICAgICAgICAgZW5kCiAgICAgICAgZW5kCiAgICAgIGVuZAogICAgICBpZiBtaW5faSAmJiAobWluIDwgZCkKICAgICAgICBwYWlyID0gW2N1ciwgbWluX2ldCiAgICAgICAgZCA9IG1pbgogICAgICAgIGggPSB7fQogICAgICAgICgwLi5jdXIpLmVhY2ggZG8gfGl8CiAgICAgICAgICBoW2NhbGNfaW5kZXgoZCxkYXRhW2ldKV0gPSBpCiAgICAgICAgZW5kCiAgICAgIGVsc2UKICAgICAgICBoW2lkeF0gPSBjdXIKICAgICAgZW5kCiAgICAgIGN1ciArPSAxCiAgICBlbmQKICAgIHBhaXIKICBlbmQKICBwdWJsaWMKICBkZWYgY2FsYyhkYXRhKQogICAgY2FsY18wKGRhdGEuc2h1ZmZsZSkKICBlbmQKZW5kCgppZiBfX0ZJTEVfXyA9PSAkMAogIGRlZiB0aW1lKG1lcywgJmJsaykKICAgIHN0YXJ0X3RpbWUgPSBUaW1lLm5vdwogICAgYmxrLmNhbGwKICAgIHB1dHMgIiVzIDogJS4yZiBzZWMuIiAlIFttZXMsIFRpbWUubm93LXN0YXJ0X3RpbWVdCiAgZW5kCiAgZGF0YSA9IFtdCiAgbiA9IDEwMDAwCiAgbi50aW1lcyBkbwogICAgZGF0YSA8PCBbUmFuZG9tLnJhbmQsIFJhbmRvbS5yYW5kXQogIGVuZAogIHRpbWUgIlJhbmRvbWl6ZWQgQ2xvc2VzdCBQYWlyKCN7bn0gaXRlbXMpIiBkbwogICAgQ2xvc2VzdFBhaXI6OmNhbGMoZGF0YSkKICBlbmQKZW5k