Al Zimmermann's Programming Contests

Circle Packing

by Al Zimmermann


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.


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.


As the organizers, we may change the rules during this contest.


Thanks to Hugo Pfoertner for helping to design the scorer and beta-testing, and to Mark Mammel for beta-testing.

Questions ?
Return to the index