Closest Point Pair Algorithm [http://www.spoj.pl/problems/CLOPPAIR/]

closest_pair.rb

def closestpair points

  px = points

  def euclid_distance pt1, pt2
    Math.sqrt ((pt1[0] - pt2[0])**2 + (pt1[1] - pt2[1])**2)
  end

  def closestsplitpair pts, minpt, dist 

    mptx = minpt[0]
    selpts = pts.select { |m| m[0] <= mptx + dist and m[0] >= mptx - dist } 

    py = selpts.sort do |m,n| 
      m[1] <=> n[1]
    end
    cp = minpt

    py.each_index do |pt1|
      (pt1+1..pt1+7).each do |pt2|
        break if pt2 >= py.length
        if pt1 != pt2 
          d = euclid_distance(py[pt1],py[pt2]) 
          if d < dist 
            cp = [py[pt1], py[pt2]]
            dist = d
          end
        end
        
      end
    end

    return cp,dist

  end
    
  if px.length == 2
    return px, euclid_distance(px[0], px[1])
  end

  dist1 = dist2 = 0xFFFFFFFF

  minpair1,dist1 = closestpair px[0..(px.size-1)/2]
  minpair2,dist2 = closestpair px[(px.size-1)/2+1 .. -1] if px.length >= 4

  if dist1 < dist2 
    minpair3, dist3 = closestsplitpair px, px[(px.size-1)/2], dist1
  else
    minpair3, dist3 = closestsplitpair px, px[(px.size-1)/2], dist2
  end

  if (dist1 <= dist2) and (dist1 <= dist3)
    return minpair1,dist1 
  elsif (dist2 <= dist1) and (dist2 <= dist3)
    return minpair2,dist2
  else
    return minpair3,dist3
  end

end

def generate_random
  n = rand(2..50000)
  testcase = []
  50000.times do 
    x = rand(-1000000..1000000)
    y = rand(-1000000..1000000)
    testcase << [x,y]
  end
  testcase
end

points_arr = generate_random

# points_arr = []
# STDIN.readline.to_i.times do 
#  points_arr << STDIN.readline.split(' ').map { |m| m.to_i}
# end

points_temp = points_arr.clone
points_arr.sort! do |m,n| 
  m[0] <=> n[0]
end

point_pair, dist = closestpair(points_arr)

pt1 = points_temp.index(point_pair[0])
pt2 = points_temp.rindex(point_pair[1])

if pt1 < pt2 
  puts("#{pt1} #{pt2} %0.6f" % dist.round(6)) 
  
else
  puts("#{pt2} #{pt1} %0.6f" % dist.round(6)) 
  
end