closest_pair.rb

# Copyright (c) 2008 Thiago Freire
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

# Program to solve the closest pair problem, in a plane and using divide and conquer techniques.
# The entry will be like:
# number_of_test_cases
# number_of_point_of_the_first_test_case
# x-coordinate y-coordinate
# x-coordinate y-coordinate
# ...
# number_of_points_of_the_second_test_case
# ...
# And the exit, for each test case, will be:
# x-coordinate y-coordinate x-coordinate y-coordinate distance

@closest = []
@points = []

def test_case()
  read_points
  
  # sort the array by the x-coordinate
  @points.sort! {|e1, e2| e1.first <=> e2.first}
  # put the first pair in the result array
  @closest = [@points[0], @points[1], point_distance(@points[0], @points[1])]
  closest_pair(@points)
  
  printf("%s %s  %.3f\n", @closest[0].join(" "), @closest[1].join(" "), @closest[2])
  @closest = []
  @points = []
end

def read_points()
  gets.to_i.times do
    point = []
    point = gets.split(' ').map! {|e| e.to_i}
    @points << point
  end
end

def closest_pair(points)
  return points if points.size <= 1
  mid = points.size / 2
  left = points[0, mid]
  right = points[mid, points.size]
  midpoint = points[mid]
  points = merge(closest_pair(left), closest_pair(right))
  
  # considering d the minimum distance and mid the middle of the array, subset will have points with the x-coordinate in the interval [mid-d,mid+d]
  subset = []
  points.each do |point|
    subset << point if (point.first - midpoint.first).abs < @closest.last
  end
  subset.each_with_index do |point,index|
    j = index + 1
    while j < subset.size and (subset[j].last - point.last) < @closest.last
      distance = point_distance(point, subset[j])
      if distance < @closest.last
        @closest = [point, subset[j], distance]
      end
      j += 1
    end
  end
  return points
end

def merge(left, right)
  left.concat(right).sort! {|e1, e2| e1.last <=> e2.last}
end

def point_distance(p1, p2)
  Math.sqrt(((p1.first - p2.first)**2) + ((p1.last - p2.last)**2))
end

gets.to_i.times do
  test_case
end