```> Had a lot of fun with this one :) My solution works by taking the average of
> all points as the center, and the farthest outlying point as the radius. An
> optimal solution is then found by moving the circle center towards the
> outlier as the radius is reduced

Well, I didn't have the time to check out how to do this the right way
(as Douglas did it). I nevertheless tried several approaches. This one
has some imprecision built-in but it turns out (in comparison with
Douglas' solution) that for random point sets, it performs more or
less well (for an incorrect semi-solution).

I also attach some code to run several solution against each other,
which is fun if you exclude the precise solutions. This requires the
script lib from http://redshift.sourceforge.net/script/.

Cool quiz BTW that made me refresh my knowledge on triangles etc. I
algorithms.

Regards,
Thomas.

My semi-solution that uses a similar approach as Justin:

def encircle(points)        # takes array of Point objects
points = points.uniq
return if points.nil? or points.empty?

x  = points.inject(0.0) {|a, p| a += p.x} / points.size
y  = points.inject(0.0) {|a, p| a += p.y} / points.size
a  = Point.new(x, y)
return Circle.new(a, 0) unless points.size > 1

f  = points.sort_by {|p| distance(a, p)}[-1]
df = distance(f, a)
b  = med(f, a)
e  = 1e-12
1000.times do
db = distance(f, b)
if points.all? {|p| distance(b, p) <= db + e}
da = distance(f, a)
if (da - db).abs < e
return Circle.new(b, db)
else
a, b = b, med(f, b)
end
else
b = med(a, b)
end
end
raise RuntimeError
end

def med(a, b)
Point.new((b.x - a.x) / 2 + a.x, (b.y - a.y) / 2 + a.y)
end

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

The code to run the tests:

#!/usr/bin/env ruby19

require 'script'

files = [
's_tml.rb',
's_frank.rb',
's_justin.rb',
's_douglas.rb',
]

def generate_samples(n)
(1..n).map { [rand - 0.5, rand - 0.5] }
end

# Numer of samples
# N = 10
N = 50
# N = 100
# N = 200

# Tolerance
E = 1e-10

# Your favourite solution, you might want to change this
F = 's_tml.rb'

sets = Array.new(N) {|i| generate_samples(i + 2)}
solutions = Hash.new {|h, k| h[k] = {}}

# Best choice per sample
winners = Hash.new {|h,k| h[k] = 0}

# Number of invalid solutions
losers = Hash.new {|h,k| h[k] = 0}

puts
files.each do |f|
print f
sets.each_with_index do |ps, i|
if i % 10 == 0
print '.'; STDOUT.flush
end
ps = ps.map {|p| script::Point.new(*p)}
v = script.encircle(ps)
if ps.any? {|p| distance(v.center, p) > v.radius + E}
losers[f] += 1
print 'x'; STDOUT.flush
end
solutions[i][f] = v
end
puts
end
puts

f_dist = 0

puts "                   %s" % files.map {|f| '%10s' % f}.join(' ')
solutions.each do |i, s|
winner = files.sort_by {|f| s[f] ? s[f].radius : 100000000}[0]
winners[winner] += 1
f_dist = f_d if f_d > f_dist
puts '%5d %10s %s (%6.4f)' % [
i,
'(%s)' % winner,
files.map {|f| s[f] && '%10.4f' % s[f].radius}.join(' '),
f_d,
]
end
puts

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

puts "Losers (invalid solutions):"
losers.each do |f, n|
puts '%10s %d' % [f, n]
end
puts

puts "Favourite vs Winner:"
puts 'Max distance: %6.4f' % f_dist
puts

```