#!/usr/bin/env ruby
# tom.luo@gmail.com
# 1/29/2010
# Facebook smallworld puzzle

House = Struct.new(:id, :lat_long, :leftNeighbour, :rightNeighbour)
TOP =3


def two_dim_tree(points, depth=0)
  return if points.size ==0
  
  axis = depth % 2 + 1
  points.sort! { |a, b| a[axis] <=> b[axis] }
  median = points.size / 2
  lat = points[median][1]
  long = points[median][2] 
  house = House.new(points[median][0], [lat,long], nil, nil)
  house.leftNeighbour = two_dim_tree(points[0...median], depth+1) # include median
  house.rightNeighbour = two_dim_tree(points[median+1..-1], depth+1) # exclude median
  return house
end

def diagnal_square(house, destination)
  return nil if house.nil? or destination.nil?
  (house.lat_long[0] - destination[0])**2 + (house.lat_long[1] - destination[1])**2
end

def get_top3(nearest, house, destination)
  d = diagnal_square(house, destination) 
  if nearest.size <= TOP || d < nearest.last[1]
    nearest.pop if nearest.size > TOP
    nearest << [house.id, d]
    nearest.sort! { |a, b| a[1] <=> b[1] }
  end
  nearest
end

$friends_nearby = []
def search(house, destination, depth=0)
  axis = depth % 2
  
  if house.leftNeighbour.nil? && house.rightNeighbour.nil? # Leaf house
    $friends_nearby = get_top3($friends_nearby, house, destination)
    return
  end
  
  if house.rightNeighbour.nil? || (house.leftNeighbour && destination[axis] <= house.lat_long[axis])
    nearer = house.leftNeighbour
    farther = house.rightNeighbour
  else
    nearer = house.rightNeighbour
    farther = house.leftNeighbour
  end
  search(nearer, destination, depth+1)
  
  if farther
    if $friends_nearby.size <= TOP || (destination[axis] - house.lat_long[axis])**2 < $friends_nearby.last[1]
      search(farther, destination, depth+1)
    end
  end
  $friends_nearby = get_top3($friends_nearby, house, destination)
end


filename = ARGV[0]
file = File.open(filename)

$friendList = []
lines = file.readlines
lines.each do |line|
  seq, lat, long = line.split()
  $friendList << [seq.to_i, lat.to_f, long.to_f]
end

root = two_dim_tree($friendList)

$friendList.sort! { |a, b| a[0] <=> b[0] }
$friendList.each do |f|
  id = f[0]
  lat = f[1]
  long = f[2]
  $friends_nearby = []
  puts "#{id} #{search(root, [lat,long])[1..TOP].collect{ |n| n[0] }.join(',')}\n"
end