--------------030201000309060301080308
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

Bill Kelly wrote:
>
>> (Benchmark code is attached...)
>
> For completeness' sake, I've uploaded the benchmark script, plus
> all the solutions... I had to tweak a few slightly to remove
> printouts and such:
>
> http://tastyspleen.net/~billk/ruby/quiz/157-smallest-circle/benchmark/

Here's my code updated with the convex hull method from Philipp which 
doesn't change the result but gives a huge speedup in the most common cases.

Lionel

--------------030201000309060301080308
Content-Type: text/plain;
 name57_lionel_bouton.rb"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename57_lionel_bouton.rb"

aW5jbHVkZSBNYXRoCgptb2R1bGUgQ29udmV4SHVsbAoKICAjIGFmdGVyIGdyYWhhbSAmIGFu
ZHJldwogIGRlZiBzZWxmLmNvbnZleF9odWxsKHBvaW50cykKICAgIGxvcCA9IHBvaW50cy5z
b3J0X2J5IHsgfHB8IHAueCB9CiAgICBsZWZ0ID0gbG9wLnNoaWZ0CiAgICByaWdodCA9IGxv
cC5wb3AKICAgIGxvd2VyLCB1cHBlciA9IFtsZWZ0XSwgW2xlZnRdCiAgICBsb3dlcl9odWxs
LCB1cHBlcl9odWxsID0gW10sIFtdCiAgICBkZXRfZnVuYyA9IGRldGVybWluYW50X2Z1bmN0
aW9uKGxlZnQsIHJpZ2h0KQogICAgdW50aWwgbG9wLmVtcHR5PwogICAgICBwID0gbG9wLnNo
aWZ0CiAgICAgICggZGV0X2Z1bmMuY2FsbChwKSA8IDAgPyBsb3dlciA6IHVwcGVyICkgPDwg
cAogICAgZW5kCiAgICBsb3dlciA8PCByaWdodAogICAgdW50aWwgbG93ZXIuZW1wdHk/CiAg
ICAgIGxvd2VyX2h1bGwgPDwgbG93ZXIuc2hpZnQKICAgICAgd2hpbGUgKGxvd2VyX2h1bGwu
c2l6ZSA+PSAzKSAmJgogICAgICAgICAgIWNvbnZleD8obG93ZXJfaHVsbC5sYXN0KDMpLCB0
cnVlKQogICAgICAgIGxhc3QgPSBsb3dlcl9odWxsLnBvcAogICAgICAgIGxvd2VyX2h1bGwu
cG9wCiAgICAgICAgbG93ZXJfaHVsbCA8PCBsYXN0CiAgICAgIGVuZAogICAgZW5kCiAgICB1
cHBlciA8PCByaWdodAogICAgdW50aWwgdXBwZXIuZW1wdHk/CiAgICAgIHVwcGVyX2h1bGwg
PDwgdXBwZXIuc2hpZnQKICAgICAgd2hpbGUgKHVwcGVyX2h1bGwuc2l6ZSA+PSAzKSAmJgog
ICAgICAgICAgIWNvbnZleD8odXBwZXJfaHVsbC5sYXN0KDMpLCBmYWxzZSkKICAgICAgICBs
YXN0ID0gdXBwZXJfaHVsbC5wb3AKICAgICAgICB1cHBlcl9odWxsLnBvcAogICAgICAgIHVw
cGVyX2h1bGwgPDwgbGFzdAogICAgICBlbmQKICAgIGVuZAogICAgdXBwZXJfaHVsbC5zaGlm
dAogICAgdXBwZXJfaHVsbC5wb3AKICAgIGxvd2VyX2h1bGwgKyB1cHBlcl9odWxsLnJldmVy
c2UKICBlbmQKCiAgcHJpdmF0ZQoKICBkZWYgc2VsZi5kZXRlcm1pbmFudF9mdW5jdGlvbihw
MCwgcDEpCiAgICBwcm9jIHsgfHB8ICgocDAueC1wMS54KSoocC55LXAxLnkpKS0oKHAueC1w
MS54KSoocDAueS1wMS55KSkgfQogIGVuZAoKICBkZWYgc2VsZi5jb252ZXg/KGxpc3Rfb2Zf
dGhyZWUsIGxvd2VyKQogICAgcDAsIHAxLCBwMiA9IGxpc3Rfb2ZfdGhyZWUKICAgIChkZXRl
cm1pbmFudF9mdW5jdGlvbihwMCwgcDIpLmNhbGwocDEpID4gMCkgXiBsb3dlcgogIGVuZAoK
ZW5kCgpjbGFzcyBQb2ludCA8IFN0cnVjdC5uZXcoOngsIDp5KQogIGRlZiBzZWxmLnJhbmRv
bQogICAgUG9pbnQubmV3KHJhbmQsIHJhbmQpCiAgZW5kCgogIGRlZiBzZWxmLmdlbmVyYXRl
X3NhbXBsZXMobikKICAgICgxLi5uKS5tYXAgeyBzZWxmLnJhbmRvbSB9CiAgZW5kCgogIGRl
ZiB0b19zCiAgICAiKCN7eH0sICN7eX0pIgogIGVuZAplbmQKCmNsYXNzIFBvdGVudGlhbENl
bnRlciA8IFN0cnVjdC5uZXcoOngsIDp5LCA6cG9pbnRzKQogIGluY2x1ZGUgTWF0aAoKICAj
IFNxdWFyZSBkaXN0YW5jZSB3aXRoIGEgcG9pbnQKICBkZWYgc3F1YXJlX2Rpc3RhbmNlKHBv
aW50KQogICAgKChwb2ludC54IC0geCkgKiogMikgKyAoKHBvaW50LnkgLSB5KSAqKiAyKQog
IGVuZAoKICAjIE1heGltdW0gc3F1YXJlIGRpc3RhbmNlIHdpdGggbXkgcG9pbnRzCiAgIyBJ
dCdzIGNhY2hlZCBiZWNhdXNlIGl0J3MgY2FsbGVkIHNldmVyYWwgdGltZXMgYW5kIGNhbiBi
ZSB2ZXJ5IGNvc3RseQogIGRlZiBtYXhfc3F1YXJlX2Rpc3RhbmNlCiAgICBAc3FfZGlzdCB8
fD0gKHBvaW50cy5tYXAgeyB8cG9pbnR8IHNxdWFyZV9kaXN0YW5jZShwb2ludCkgfS5tYXgp
CiAgZW5kCgogICMgQ29tcHV0ZSB0aGUgYmVzdCBtb3ZlIHdpdGggZ2l2ZW4gZGlzdGFuY2Ug
KHJvKQogICMgYW5kIGFuZ2xlcyAodGhldGFzKQogICMgcmV0dXJucyBuaWwgaWYgbm9uZSBp
cyBiZXR0ZXIgdGhhbiB0aGUgY3VycmVudCBwb3NpdGlvbgogIGRlZiBiZXN0X21vdmUocm8s
IHRoZXRhcykKICAgIHBvdGVudGlhbF9tb3ZlcyA9IHRoZXRhcy5tYXAgeyB8dGhldGF8CiAg
ICAgIG5ld194ID0geCArIChybyAqIGNvcyh0aGV0YSkpCiAgICAgIG5ld195ID0geSArIChy
byAqIHNpbih0aGV0YSkpCiAgICAgIFBvdGVudGlhbENlbnRlci5uZXcobmV3X3gsbmV3X3ks
cG9pbnRzKQogICAgfQogICAgY2hvb3NlX21vdmVfMShwb3RlbnRpYWxfbW92ZXMpCiAgZW5k
CgogICMgRHVtYmVyLCBmYXN0ZXIKICBkZWYgY2hvb3NlX21vdmVfMShwb3RlbnRpYWxfbW92
ZXMpCiAgICBwb3RlbnRpYWxfbW92ZXMuZGV0ZWN0IHsgfG1vdmV8CiAgICAgIG1heF9zcXVh
cmVfZGlzdGFuY2UgPiBtb3ZlLm1heF9zcXVhcmVfZGlzdGFuY2UKICAgIH0KICBlbmQKCiAg
IyBMb29rIGZvciB0aGUgc2hvcnRlc3QgcGF0aCwgc2xvd2VyICh+MS40eCBvbiBhdmVyYWdl
IHdpdGggbWFueSBwb2ludHMpCiAgZGVmIGNob29zZV9tb3ZlXzIocG90ZW50aWFsX21vdmVz
KQogICAgcG90ZW50aWFsX21vdmVzLnJlamVjdCEgeyB8bW92ZXwKICAgICAgbWF4X3NxdWFy
ZV9kaXN0YW5jZSA8PSBtb3ZlLm1heF9zcXVhcmVfZGlzdGFuY2UKICAgIH0KICAgIHBvdGVu
dGlhbF9tb3Zlcy5taW4geyB8YzEsYzJ8CiAgICAgIGMxLm1heF9zcXVhcmVfZGlzdGFuY2Ug
PD0+IGMyLm1heF9zcXVhcmVfZGlzdGFuY2UKICAgIH0KICBlbmQKCiAgIyBDaGVjayB0aGF0
IHRoZSBnaXZlbiBvZmZzZXQgaXMgYmlnIGVub3VnaCB0byBtb3ZlCiAgIyB0aGUgY3VycmVu
dCBwb3NpdGlvbgogICMgKGZsb2F0aW5nIHBvaW50IHJvdW5kaW5nIGVycm9ycyBwcmV2ZW50
IGluZmluaXRlIHByZWNpc2lvbi4uLikKICBkZWYgY2FuX2JlX21vdmVkX2J5KG9mZnNldCkK
ICAgICgoeCArIG9mZnNldCkgIT0geCkgfHwgKCh5ICsgb2Zmc2V0KSAhPSB5KQogIGVuZAoK
ICBkZWYgdG9fcwogICAgIigje3h9LCAje3l9KSIKICBlbmQKZW5kCgpjbGFzcyBDaXJjbGUg
PCBTdHJ1Y3QubmV3KDpjZW50ZXIsIDpyYWRpdXMpCiAgZGVmIHRvX3MKICAgICJ7Y2VudGVy
OiN7Y2VudGVyfSwgcmFkaXVzOiN7cmFkaXVzfX0iCiAgZW5kCmVuZAoKZGVmIGNob3NlX29y
aWdpbmFsX2NlbnRlcl9hbmRfbW92ZV9hbW91bnQocG9pbnRzKQogICMgU3RhcnQgd2l0aCBh
IGdvb2QgcG90ZW50aWFsIChhcm91bmQgdGhlIG1pZGRsZSBvZiB0aGUgcG9pbnQgY2xvdWQp
CiAgbWF4X3ggPSBwb2ludHMubWFwe3xwfCBwLnh9Lm1heAogIG1pbl94ID0gcG9pbnRzLm1h
cHt8cHwgcC54fS5taW4KICB4ID0gKG1heF94ICsgbWluX3gpIC8gMgogIG1heF95ID0gcG9p
bnRzLm1hcHt8cHwgcC55fS5tYXgKICBtaW5feSA9IHBvaW50cy5tYXB7fHB8IHAueX0ubWlu
CiAgeSA9IChtYXhfeSArIG1pbl95KSAvIDIKICBjZW50ZXIgPSBQb3RlbnRpYWxDZW50ZXIu
bmV3KHgsIHksIHBvaW50cykKICAjIFRoZSBvcmlnaW5hbCBkaXNwbGFjZW1lbnQgdmFsdWUg
aXMgYmFzZWQgb24gdGhlIGZhY3QgdGhhdCBhIHRydWx5CiAgIyByYW5kb20gZGlzdHJpYnV0
aW9uIGdldHMgYSBtZWFuIHZhbHVlIHdpdGggYSBwcmVjaXNpb24gb2YgdGhpcyBvcmRlci4K
ICAjIFRoZSBhY3R1YWwgY2VudGVyIGlzIHByb2JhYmx5IHJlYWNoYWJsZSB3aXRoIGEgZmV3
IG9mIHRoZXNlIHN0ZXBzCiAgbW92ZV9hbW91bnQgPSAoKG1heF95IC0gbWluX3kpICsgKG1h
eF94IC0gbWluX3gpKSAvIHBvaW50cy5zaXplCiAgcmV0dXJuIFtjZW50ZXIsIG1vdmVfYW1v
dW50XQplbmQKCiMgTG9vayBmb3IgdGhlIGJlc3QgY2VudGVyIGJ5IG1pbmltaXppbmcKIyBp
dHMgbWF4aW11bSBkaXN0YW5jZSB3aXRoIHRoZSBnaXZlbiBwb2ludHMKIyBUaGlzIGlzIHRo
ZSBzYW1lIGFzIG1pbmltaXppbmcgaXRzIHNxdWFyZQojICh0aGUgbWF4aW11bSBvZiB0aGUg
c3F1YXJlIGRpc3RhbmNlcykKIyBUaGlzIGNhbiBiZSBzZWVuIGFzIGEgZGljaG90b215IG9u
IGEgMi1kaW1lbnNpb25hbCBzcGFjZQpkZWYgZW5jaXJjbGUocG9pbnRzKQogIGNlbnRlciwg
cm8gPSBjaG9zZV9vcmlnaW5hbF9jZW50ZXJfYW5kX21vdmVfYW1vdW50KHBvaW50cykKICAj
IFdlJ2xsIG1vdmUgd2l0aCBwb2xhciBjb29yZGluYXRlcyAoZGlzdGFuY2UgKyBhbmdsZSA6
IHJvL3RoZXRhKQogICMgSG93IG1hbnkgZGlyZWN0aW9ucyBkbyB3ZSBmb2xsb3c/CiAgIyBl
YWNoIG5ldyBhbmdsZSBjcmVhdGVzIGEgbmV3IChjb3N0bHkpIG1heF9zcXVhcmVfZGlzdGFu
Y2UgY2FsbAogICMgc28gd2UgdGFrZSB0aGUgbWluaW11bSBuZWVkZWQgdG8gbW92ZSBhcm91
bmQgYW5kIGNsaW1iIHRoZQogICMgc3F1YXJlX2Rpc3RhbmNlIGdyYWRpZW50OiAzCiAgYW5n
bGVfY291bnQgPSAzCiAgdGhldGFzID0gKDEuLmFuZ2xlX2NvdW50KS5tYXAgeyB8Y3wgKDIg
KiBjICogTWF0aDo6UEkpIC8gYW5nbGVfY291bnR9CiAgaXRlciA9IDAKICAjIFRyYWNlIG91
ciBtb3ZlcwogIGNlbnRlcl9saXN0ID0gW10KCiAgbG9vcCBkbwogICAgY2VudGVyX2xpc3Qg
PDwgY2VudGVyCiAgICBpdGVyICs9IDEKICAgIyBwdXRzICIje2l0ZXJ9OiAje2NlbnRlci5t
YXhfc3F1YXJlX2Rpc3RhbmNlfSIKICAgICMgSXMgdGhlcmUgYSBiZXN0IG1vdmUgYXZhaWxh
YmxlID8KICAgIGlmIG5ld19jZW50ZXIgPSBjZW50ZXIuYmVzdF9tb3ZlKHJvLCB0aGV0YXMp
CiAgICAgIGNlbnRlciA9IG5ld19jZW50ZXIKICAgIGVsc2UKICAgICAgcm8gLz0gMgogICAg
ICAjIFdlIHN0b3Agd2hlbiBybyBiZWNvbWVzIHRvbyBzbWFsbCB0byBtb3ZlIHRoZSBjZW50
ZXIKICAgICAgYnJlYWsgdW5sZXNzIGNlbnRlci5jYW5fYmVfbW92ZWRfYnkocm8pCiAgICBl
bmQKICBlbmQKICMgcHV0cyAiQ2lyY2xlIGZvdW5kIGluICN7aXRlcn0gaXRlcmF0aW9ucyIK
ICByZXR1cm4gWyBDaXJjbGUubmV3KGNlbnRlciwgc3FydChjZW50ZXIubWF4X3NxdWFyZV9k
aXN0YW5jZSkpLAogICAgICAgICAgIGNlbnRlcl9saXN0IF0KZW5kCgppZiAkMCA9PSBfX0ZJ
TEVfXwoKICAjIFVzZXMgMTAgcG9pbnRzIGJ5IGRlZmF1bHQKICBQT0lOVF9DT1VOVCA9IChB
UkdWWzBdLnRvX2kgPT0gMCkgPyAxMCA6IEFSR1ZbMF0udG9faQoKICBwb2ludHMgPSBQb2lu
dC5nZW5lcmF0ZV9zYW1wbGVzKFBPSU5UX0NPVU5UKQogIGh1bGwgPSBDb252ZXhIdWxsLmNv
bnZleF9odWxsKHBvaW50cykKICB0ID0gVGltZS5ub3cKICBjaXJjbGUsIGNlbnRlcl9saXN0
ID0gZW5jaXJjbGUoaHVsbCkKICBwdXRzIGNpcmNsZQogIHB1dHMgIkZvdW5kIGluOiAje1Rp
bWUubm93IC0gdH1zIgogIAogICMgR2VuZXJhdGUgYSBHbnVQbG90IGNvbW1hbmQgZmlsZSB0
byBzZWUgdGhlIHJlc3VsdAogIGYgPSBGaWxlLm9wZW4oJ3Bsb3Rjb21tYW5kLmNtZCcsICd3
JykKICBmLnByaW50IDw8RU9GCnNldCBwYXJhbWV0cmljCnNldCBzaXplIHNxdWFyZQpzZXQg
eHJhbmdlIFstMC4yOjEuMl0Kc2V0IHlyYW5nZSBbLTAuMjoxLjJdCnNldCBtdWx0aXBsb3QK
cGxvdCAiLSIKI3twb2ludHMubWFwIHsgfHB8ICIje3AueH0gI3twLnl9IiB9LmpvaW4oIlxu
Iil9CmVuZApwbG90ICItIiB3aXRoIGxpbmVzCiN7Y2VudGVyX2xpc3QubWFwIHsgfHB8ICIj
e3AueH0gI3twLnl9IiB9LmpvaW4oIlxuIil9CmVuZApwbG90IFswOjIqcGldIAooc2luKHQp
KiN7Y2lyY2xlLnJhZGl1c30pKyN7Y2lyY2xlLmNlbnRlci54fSwoY29zKHQpKiN7Y2lyY2xl
LnJhZGl1c30pKyN7Y2lyY2xlLmNlbnRlci55fQpzZXQgbm9tdWx0aXBsb3QKRU9GCiAgZi5j
bG9zZQogIAogIHB1dHMgPDxFT0YKdXNlICdnbnVwbG90IC1wZXJzaXN0IHBsb3Rjb21tYW5k
LmNtZCcgdG8gc2VlCnRoZSBjaXJjbGUsIHBvaW50cyBhbmQgcGF0aCB0byB0aGUgY2VudGVy
CkVPRgogIAplbmQKCgo--------------030201000309060301080308--