```Hi,

Since Matthew has a cold, I decided to take another look at my
"solution". Accuracy hasn't changed because the idea is exactly the
same as before, but speed is at least measurable now. Well, overall
performance is still abominable but since I started it (i.e. posted
the previous version) I thought I could also post this slightly more
complex version. I also included some hopefully correct code for ruby
1.8 compatibility. The use of complex could be easily avoided of
course.

Maybe of more interest to you: I also include a revised version of my
accuracy checker that makes use of Lionel's more sophisticated sample
generator. My "solution" performs especially bad on "random on disk"
and "2d gaussian" it seems. Oh well.

Regards,
Thomas.

========================================================================

require 'complex'

class Point < Struct.new(:x, :y)
def self.random
Point.new(rand, rand)
end

def to_s
"(#{x}, #{y})"
end

def self.from_complex(c)
self.new(c.real, c.image)
end
end

def to_s
end
end

def encircle(points)        # takes array of Point objects
return if points.nil? or points.empty?
return Circle.new(points[0], 0) if points.size == 1

points = prepare(points)
a, ar  = points_max_dist_center(points)
return Circle.new(Point.from_complex(a), ar) unless points.size >
2

points = points.sort_by {|p| -(a - p).abs}
f      = points[0]
points.delete(f)
zz = nil
zr = 0
points.each do |p|
aang = (a - f).angle
pang = (p - f).angle
phi  = pang - aang
rd   = (f - p).abs / 2.0
rr   = rd / Math.cos(phi)
if rr > zr
ra = f.real  + rr * Math.cos(aang)
rb = f.image + rr * Math.sin(aang)
zz = Complex(ra, rb)
zr = rr
end
end
return Circle.new(Point.from_complex(zz), zr)
end

def points_max_dist_center(points)
m, n = points.combination(2).sort_by {|a, b| -(a - b).abs}[0]
a = (m + n) / 2.0
d = (a - m).abs
return [a, d]
end

def prepare(points)
points = points.uniq
points.map! {|p| Complex(*p.to_a)}
i = 3
while i < points.size
p1, p2, p3 = points[i-3, i]
points.delete_if {|p| in_triangle?(p1, p2, p3, p)}
i += 1
end
return points
end

def in_triangle?(a, b, c, p)
return false if a.nil? or b.nil? or c.nil? or p.nil? or a == p or
b == p or c == p
u = (a - b).angle
l = (a - c).angle
x = (a - p).angle
return false unless x.between?(l, u)
u = (c - a).angle
l = (c - b).angle
x = (c - p).angle
return x.between?(l, u)
end

if RUBY_VERSION < '1.9.0'
class ::Array

def combination(n)
out = []
size.times do |i|
if n > 1
rest = self[i + 1, size]
if rest.size >= n - 1
tails = rest.combination(n - 1)
end
else
end
end
out
end

end
end

if __FILE__ == \$0
points = []
ARGV.each {|p| points << Point.new(*p.split(/,/).map{|c| c.to_f})}
c = encircle(points)
p c
end

========================================================================

#!/usr/bin/env ruby19

require 'mathn'

E = 1e-10

num_runs = 10
num_samples = 100
# num_runs = 10
# num_samples = 1000

module PHILIPP ; eval(File.read('s_philip.rb'))  ;  end
module LIONEL ;  eval(File.read('s_lionel.rb'))    ;  end
module DOUG ;    eval(File.read('s_douglas.rb'))     ;  end
module FRANK ;   eval(File.read('s_frank.rb'))    ;  end
module JUSTIN ;  eval(File.read('s_justin.rb'))    ;  end
module BILL ;    eval(File.read('s_billk.rb'))       ;  end
module BILL2 ;   eval(File.read('s_billk2.rb'))       ;  end
module THOMAS ;  eval(File.read('quiz157l.rb'))        ;  end
module THOMAS2 ;  eval(File.read('quiz157s.rb'))        ;  end

namespaces = [
THOMAS,
THOMAS2,
FRANK,
JUSTIN,
LIONEL,
LIONEL4,
DOUG,
PHILIPP,
PHILIPP2,
BILL,
BILL2,
]

class Point < Struct.new(:x, :y)
def self.random(type=0)
case type
when 1
ro = rand / 2
theta = Math::PI * 2 * rand
Point.new(ro * Math::cos(theta) + 0.5, ro *
Math::sin(theta) + 0.5)
else
Point.new(rand, rand)
end
end

def to_s
"(#{x}, #{y})"
end
end

def generate_samples(mod, coords)
coords.map {|xy| mod::Point.new(*xy)}
end

def distance(p1, p2)
Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2)
end

distributions = {
"Random on square" =>
(1..num_runs).map {(1..num_samples).map {[rand, rand]}},
"Random on disk" =>
(1..num_runs).map {(1..num_samples).map {
ro = rand(0.5)
theta = Math::PI * 2 * rand
[ ro * Math::cos(theta), ro * Math::sin(theta)]
}
},
"Random on circle" =>
(1..num_runs).map {(1..num_samples).map {
theta = Math::PI * 2 * rand
[ Math::cos(theta), Math::sin(theta)]
}
},
"2D Gaussian" =>
(1..num_runs).map {(1..num_samples).map {
ro = Math::sqrt(-2 * Math::log(rand))
theta = Math::PI * 2 * rand
[ ro * Math::cos(theta), ro * Math::sin(theta)]
}
},
}

def prepare_pointsets(namespaces, raw_coords, num_runs)
pointsets = {}
namespaces.each do |mod|
pointsets[mod.name] = (0...num_runs).map do |i|
generate_samples(mod, raw_coords[i])
end
end
pointsets
end

puts
distributions.each { |name,raw_coords|
results = Hash.new {|h, k| h[k] = {}}
winners = Hash.new {|h,k| h[k] = 0}

puts "-- #{name} --"
pointsets = prepare_pointsets(namespaces, raw_coords, num_runs)
solutions = {}
namespaces.each {|mod| solutions[mod.name] = Class.new { include
mod }.new}
namespaces.each do |mod|
name = mod.name
solution = solutions[name]
num_runs.times do |i|
points = pointsets[name][i]
val = solution.encircle(points)
results[i][mod] = val
end
end

f_dist = Hash.new {|h,k| h[k] = []}

results.each do |i, s|
cwinner = namespaces.sort_by {|f| s[f] ? s[f].radius :
100000000}
winners[cwinner[0]] += 1
cwinner.each_cons(2) do |a,b|
winners[b] += 1
else
break
end
end

namespaces.each do |fav|
100
f_dist[fav] << f_d
end
end

puts "Winners (best circle):"
winners.each do |f, n|
puts '%10s %d' % [f, n]
end
puts

puts "Fav: %s" % namespaces.join(', ')
puts 'Min: %s' % f_dist.map {|fav, d| '%6.2f' % d.min}.join(', ')
puts 'Max: %s' % f_dist.map {|fav, d| '%6.2f' % d.max}.join(', ')
puts 'Avg: %s' % f_dist.map {|fav, d| '%6.2f' % (d.inject(0.0){|
a,d| a + d} / d.size)}.join(', ')
puts

}

```