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