Al Zimmermann's Programming Contests
Circle Packing
by Al Zimmermann
Introduction
Pack N non-overlapping discs with radii from 1 to N into as small a circle as possible.
The Task
You must submit x and y coordinates for 5 to 50 discs, so that the enclosing circle is minimal.
No discs must be concentric (that is: they have the same center).
The center of the circumscribing circle is (0,0), but the scorer doesn't translate your discs.
The first coordinates are radius 1 disc's center, the second are radius 2, etc...
You don't have to mention the radius sizes.
The coordinates can have 20 characters at most (including period and sign), and the scorer scales them in order to avoid collisions into your submitted set.
Here is an example with 4 discs:
-0.09657434582230290 -0.56182472509981420
-0.21190854170729230 0.65952164349456150
-0.57142857142817450 -0.00000070672180066
0.42857142857148220 0.00000000000000000
The Scoring System
When you submit a set of discs for a given N, the scorer will compute the smallest circumscribing circle, by automatically scaling your input.
Your score for this N will be equal to:
Q=(best submitted radius)/(your submitted radius)
Score = (0.7 * Q) + (0.1 * Q16) + (0.1 * Q128) + (0.1 * Q1024)
Total Scoring
When you submit a set of discs, its score is automatically computed.
If you do not submit for a particular value of N, you will receive a 0 for that value of N.
Your score for a particular value of N will be equal to the value given by the formula above.
Hence the best total score you can get is 46.
Prizes
First prize is $250, second prize is $150.
In case of a tie, the entrant who reached the tied score first wins.
At the end of every week for the first 10 weeks, the score leader will win $10.
All prizes will be paid via Paypal.
Organization
As the organizers, we may change the rules during this contest.
Thanks
Thanks to Hugo Pfoertner for helping to design the scorer and beta-testing, and to Mark Mammel for beta-testing.
