> 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
wish a had had more time so that I could also read up on appropriate
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
    script = Script.load(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
            v.radius += 1000.0
        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_d = (s[F].radius - s[winner].radius).abs
    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