Cut a silicon wafer into dies When manufacturing chips, circular silicon wafers are cut into dies of needed size:



The goal of this challenge is maximizing the number of whole dies that can be cut from a wafer of a given diameter.

The machine puts the wafer into an angular compartment:

_____________________
|     xxxxxx
|  xxxxxxxxxxxx
| xxxxxxxxxxxxxx
|xxxxxxxxxxxxxxxx
|xxxxxxxxxxxxxxxx
| xxxxxxxxxxxxxx
|  xxxxxxxxxxxx
|     xxxxxx     (this ascii art is meant to be a perfect circle)


It measures a distance dx from the left edge, and makes a vertical cut. Then it makes the needed number of additional vertical cuts, with spacing of the needed width. It makes the horizontal cuts in the same way: first one at a distance dy, and then with spacing of height.

The material remains perfectly still during the cutting: it's not allowed to move some slices of material before making the perpendicular cuts.

The machine has a stepper motor that works at absolute accuracy but can only go integer-sized distances.

Make a program or a subroutine that gets (or reads) the following parameters:


Wafer diameter
Die width
Die height


and outputs (or prints)


dx - horizontal starting position
dy - vertical starting position


such that the number of rectangular dies is maximal.

Some fine points:


If a corner of a die lies exactly on the circumference of the circle, the die is considered usable (rectangular)
No edge cases: you can assume that the wafer's diameter is even; at least one die can be cut out; also make other reasonable assumptions
All sizes are integer numbers of millimeters; maximum wafer diameter is 450


Shortest code wins!

P.S. The code must finish running in a reasonable amount of time, e.g. over a weekend (2 days) - for wafer diameter equal to 300.

P.P.S. If there are several different output values that are optimal, the code must output one of them - no need to output all of them!

Test cases:

Wafer diameter 8, die size 2 x 2 =&gt; dx = 0, dy = 1 (6 dies)
Wafer diameter 20, die size 5 x 4 =&gt; dx = 1, dy = 2 (10 dies)
Wafer diameter 100, die size 12 x 12 =&gt; dx = 9, dy = 3 (41 dies)
Wafer diameter 300, die size 11 x 11 =&gt; dx = 7, dy = 7 (540 dies) - a realistic example
Wafer diameter 340, die size 15 x 8 =&gt; dx = 5, dy = 2 (700 dies) - a Pythagorean triple
Wafer diameter 300, die size 36 x 24 =&gt; dx = 2, dy = 6 (66 dies) - full-frame sensors


Here is a visualization of the last test case:
Python 2.7, 317

Here is my solution. Could be golfed a bit more, I think - but I like the solving better than the golfing. Suggestions are welcome. 

I solve it using brute force, iterating over all dx and dy and then counting by column. It all runs pretty fast (&lt;0,05 sec. on my Mac).

Code:

import math as m
def D(d,w,h):
 r=d/2
 s=[0,0,0]
 for dx in range(0,w):
  for dy in range(0,h):
   t=0
   for c in range(1,int(d/w)+1):
    l=r-dx-(c-1)*w
    if l&lt;w/2:
     l-=w
    if abs(l)&lt;=r:
     f=r*m.sin(m.acos(1.0*l/r));t+=int((2.0*f-(dy+m.ceil((r-dy-f)/h)*h+f-r))/h)
   if t&gt;s[0]:
    s=[t,dx,dy]
 return s


A main to test and profile the given cases:

def runTestcases():
    for d,w,h in [[8,2,2],[20,5,4],[100,12,12],[300,11,11],[340,15,8],[300,36,24]]:
        S=D(d,w,h)
        print "Wafer diameter {}, die size {} x {} =&gt; dx = {}, dy = {} ({} dies)".format(d,w,h,S[1],S[2],S[0])

def main():
    import cProfile
    cProfile.run("runTestcases()")

if __name__ == "__main__":
    main()


And its output:

Wafer diameter 8, die size 2 x 2 =&gt; dx = 0, dy = 1 (6 dies)
Wafer diameter 20, die size 5 x 4 =&gt; dx = 1, dy = 2 (10 dies)
Wafer diameter 100, die size 12 x 12 =&gt; dx = 0, dy = 8 (41 dies)
Wafer diameter 300, die size 11 x 11 =&gt; dx = 7, dy = 7 (540 dies)
Wafer diameter 340, die size 15 x 8 =&gt; dx = 5, dy = 2 (700 dies)
Wafer diameter 300, die size 36 x 24 =&gt; dx = 2, dy = 6 (66 dies)
         55354 function calls in 0.049 seconds