Circle packing in a rectangle

Question

Your task is to write a program that finds the largest radius that N circles can have and still fit inside of a rectangle that is X by Y pixels large. (similar to this wikipedia article) Your program must find the largest possible radius and optimal position of these N circles so that

1. No two circles overlap
2. All of the circles fit inside of the rectangle.

Your program should then print this to the console:

Highest possible radius: <some_number>
Circle 1 Focus: (x, y)
Circle 2 Focus: (x, y)
...
Circle N-1 Focus: (x, y)
Circle N Focus: (x, y) 

(Obviously, you must replace some_number with the radius your program calculates, N with the number of circles you end up using, and x and y with the actual coordinates of the circle)

Lastly, it should create and save a picture with these circles drawn.

Rules:

1. This program must run with any size of rectangle, and any number of circles and still get a valid answer. You can use command line arguments, user input, hard coded variables, or anything else you want.

2. If any circle overlaps or does not fit entirely inside of the box, your submission is invalid.

3. Each circle must have the same radius.

4. Just to make this reasonable and do-able, all numbers must be precise to the 2nd decimal place.

This is code golf, so shortest program (as of 10/28/2014) wins.

Answer 1

JavaScript 782 725 characters

first post, be gentle!

The program is now called via the wrapped function. Eg: (function(e,f,g){...})(100,200,10).

function C(e,f,g,c,a,d){if(0>g-a||g+a>e||0>c-a||c+a>f)return d;for(var b in d)if(Math.sqrt(Math.pow(d[b].x-g,2)+Math.pow(d[b].y-c,2))<2*a)return d;d.push({x:g,y:c});for(b=0;b<Math.PI;)XX=Math.cos(b)*a*2+g,YY=Math.sin(b)*a*2+c,d=C(e,f,XX,YY,a,d),b+=.01;return d}
(function(e,f,g){var c=e+f,a,d;for(a=[];a.length<g;)a=d=c,a=C(e,f,a,d,c,[]),c-=.01;console.log("Highest possible radius: "+Math.round(100*c)/100);e='<svg width="'+e+'" height="'+f+'"><rect width="'+e+'" height="'+f+'" style="fill:red" />';for(var b in a)console.log("Circle "+b+" Focus: ("+Math.round(100*a[b].x)/100+", "+Math.round(100*a[b].y)/100+")"),e+='<circle cx="'+a[b].x+'" cy="'+a[b].y+'" r="'+c+'" fill="blue" />';console.log(e+"</svg>")})(400,300,13);

Test 1

(function(e,f,g){...})(200,200,4)

Highest possible radius: 49.96
Circle 1 Focus: (49.97, 49.97) 
Circle 2 Focus: (149.91, 49.97) 
Circle 3 Focus: (149.99, 149.91) 
Circle 4 Focus: (50.05, 149.91) 
<svg width="200" height="200"><rect width="200" height="200" style="fill:blue;" /><circle cx="49.97000000021743" cy="49.97000000021743" r="49.960000000217434" fill="white" /><circle cx="149.9100000006523" cy="49.97000000021743" r="49.960000000217434" fill="white" /><circle cx="149.98958489212322" cy="149.90996831285986" r="49.960000000217434" fill="white" /><circle cx="50.04958489168835" cy="149.90996831285986" r="49.960000000217434" fill="white" /></svg>

Obviously we would expect the radius to be exactly 50, but for reasons discussed in the question's comments, I couldn't reasonably make it happen. The SVG looks like this...

Test 2

(function(e,f,g){...})(100,400,14)

Highest possible radius: 26.55
Circle 1 Focus: (26.56, 26.56) 
Circle 2 Focus: (79.68, 26.56) 
Circle 3 Focus: (132.8, 26.56) 
Circle 4 Focus: (185.92, 26.56) 
Circle 5 Focus: (239.04, 26.56) 
Circle 6 Focus: (292.16, 26.56) 
Circle 7 Focus: (345.28, 26.56) 
Circle 8 Focus: (372.63, 72.1) 
Circle 9 Focus: (319.52, 73.25) 
Circle 10 Focus: (265.47, 72.64) 
Circle 11 Focus: (212.35, 73.25) 
Circle 12 Focus: (159.23, 72.64) 
Circle 13 Focus: (106.11, 73.25) 
Circle 14 Focus: (52.99, 72.64) 
<svg width="400" height="100"><rect width="400" height="100" style="fill:blue;" /><circle cx="26.560000000311106" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="79.68000000093332" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="132.80000000155553" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="185.92000000217774" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="239.04000000279996" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="292.16000000342217" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="345.2800000040444" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="372.6271770491687" cy="72.09972230654316" r="26.550000000311105" fill="white" /><circle cx="319.5195599732359" cy="73.24663493712801" r="26.550000000311105" fill="white" /><circle cx="265.47097406711805" cy="72.63752174440503" r="26.550000000311105" fill="white" /><circle cx="212.35454341475625" cy="73.25330971030218" r="26.550000000311105" fill="white" /><circle cx="159.23097406587362" cy="72.63752174440503" r="26.550000000311105" fill="white" /><circle cx="106.11454341351183" cy="73.25330971030218" r="26.550000000311105" fill="white" /><circle cx="52.99097406462921" cy="72.63752174440503" r="26.550000000311105" fill="white" /></svg>

And the SVG looks like this...

Test 3

(function(e,f,g){...})(400,400,3)

Highest possible radius: 101.68
Circle 1 Focus: (101.69, 101.69) 
Circle 2 Focus: (298.23, 153.98) 
Circle 3 Focus: (154.13, 298.19) 
<svg width="400" height="400"><rect width="400" height="400" style="fill:blue;" /><circle cx="101.69000000059772" cy="101.69000000059772" r="101.68000000059772" fill="white" /><circle cx="298.2343937547503" cy="153.97504264473156" r="101.68000000059772" fill="white" /><circle cx="154.13153961740014" cy="298.19269546075066" r="101.68000000059772" fill="white" /></svg>

And the SVG looks like this...

They aren't all pretty.

How it works

Ungolfed code below. This program has two assumptions:

1. One circle will always be in the corner. This seems like a pretty safe bet.
2. Every circle will always be touching another circle. I don't see why they wouldn't be.

The program starts by calculating a large radius based on the box dimensions. It then tries to fit one circle in the corner of the box. If that circle fits, it extends a diameter line from that circle and tries to create a circle at the end of the line. If the new circle fits, another line will be extended from the new circle. If it doesn't fit, the line will swing 360 degrees, checking for open spaces. If the box fills up before the desired number of circles are created, the radius is reduced and it all starts over again.

Ungolfed Code (snippet)

// this functions attempts to build a circle
// at the given coords. If it works, it will
// spawn additional circles.
function C(x, y, X, Y, r, cc){

 // if this circle does not fit in the rectangle, BAIL
 if(X-r < 0 || X+r > x || Y-r < 0 || Y+r > y)
  return cc;
 
 // if this circle is too close to another circle, BAIL
 for(var c in cc){
  if( Math.sqrt(Math.pow(cc[c].x - X, 2) + Math.pow(cc[c].y - Y, 2)) < (r*2) )
   return cc;
 }
 
 // checks passed so lets call this circle valid and add it to stack
 cc.push({"x": X, "y": Y});
 
 // now rotate to try to find additional spots for circles
 var a = 0; // radian for rotation
 while(a < Math.PI){
  XX = Math.cos(a)*r*2 + X;
  YY = Math.sin(a)*r*2 + Y;
  cc = C(x, y, XX, YY, r, cc);
  a += .01; // CHANGE FOR MORE OR LESS PRECISION
 }
 
 return cc;
}

// this function slowly reduces the radius
// and checks for correct solutions
// also prints svg graphic code

(function B(x, y, n){

 var r = x + y; // pick a big radius
 var X, Y; // these are the coords of the current circle. golf by combining this with `var r..`?
 var cc = []; // array of coordinates of the circles
 
 // while we cant fit n circles, reduce the radius and try again
 while(cc.length < n){
  X = Y = r;
  cc = C(x, y, X, Y, r, []);
  r-=.01; // CHANGE FOR MORE OR LESS PRECISION
 }
 
 console.log('Highest possible radius: ' + Math.round(r*100)/100);
 var s = '<svg width="' + x + '" height="' + y + '"><rect width="' + x + '" height="' + y + '" style="fill:red" />';
 for(var c in cc){
  console.log('Circle '+c+' Focus: (' + Math.round(cc[c].x*100)/100 + ', ' + Math.round(cc[c].y*100)/100 + ')');
  s += '<circle cx="' + cc[c].x + '" cy="' + cc[c].y + '" r="' + r + '" fill="blue" />';
 }
 s += '</svg>';
 console.log(s);
 document.write(s);
})(150, 150, 5);