/* (p) Jan-Mark Wams
** Squaring The Circle
**
** This is not truely a solution to squaring the circle, but a
** calculation of howmany steps it takes to fill a circle with
** rectangles if the rectangles are confined within a bigger circle.
**
** This algorithm is te result of five minutes of thinking and ten
** minutes of hacking. I don't think it gives an optimal solution for
** minimizing the number of rectangles, I am no Kochański. I just
** needed to see if it is feasable to write a round loop function with
** a simple set of rectangles. In my best ASCI art:
**                   ,,,,,,,,,,,,, 
**               ,,, ______O______ ,,,
**             ,,,  |   '''''''  A|  ,,,
**          ,,, ____|''         ''|____,,,
**        ,,   | '''|             |'''B|   ,,
**       ,   __|'   |             |   '|__   ,
**      ,   | '|    |             |    |'C|   ,  
**      ,   |' |    |             |    | '|   ,
**      '   ,  |    |             |    |  ,   '
**      '   |, |    |             |    | ,|   '
**      '   | ,|    |             |    |, |   '  
**       '   --|,   |             |   ,|--   '
**        ''   | ,, |             | ,, |   ''
**          ''' ----|,,         ,,|---- '''
**             '''  |   ,,,,,,,   |  '''
**               ''' ------------- '''
**                   '''''''''''''
** Squint and you will see two concentric circles and five
** rectangles. Think and you will see three (largely overlapping
** rectangles). Since covering the inner circle with rectangles this
** way is higly point semetric calculating a 45 degree segment would
** suffice. However since we have to round the program calculates a 90
** degree angle.
**
** The algorith starts at point O and calculates A, B, C, ...
**
** Note that a real good program would actually take antialiassing
** into account which might lower the number of rectangles.
**
** If you see an easy way to do that or any other improvement, go for
** it!
*/
#include <stdio.h>
#include <math.h>

int calc_print_n(int print, int border, int outer_r)
{
  int inner_r = outer_r - border;
  int x = 0;
  int y;
  int new_x;
  int n_rectangles = 0;

  while (x < inner_r) {
    /* Calc y to touch of just peek through the inner circle. */
    y = ceil(sqrt((inner_r * inner_r) - (x * x)));

    /* Calc new new_x to just within or on the outer circle. */
    new_x = floor(sqrt((outer_r * outer_r) - (y * y)));
    
    /* Print the square. */
    n_rectangles += 1;

    if (print)
      printf("[%d,%d],", new_x * 2, y * 2);
    
    x = new_x;
  }

  return n_rectangles;
}


int main(int ac, char **av)
{
  int border;
  int min, r, max;  /* Max always leads to n > 10. */
  int n;

  /* For borders 3 to 6 calc the maximum (outer) radius reachable with
  ** ten (overlapping)  rectangles. 
  */
  for (border = 2; border < 12; border++) {
    r = min = border * 15; 
    max = min * 2;
    for(;;) {
      n = calc_print_n(0, border, r);
      if (max == r + 1 && n == 10) break;
      if      (n <= 10) { min = r; r = (r + max) / 2; }
      else if (n > 10)  { max = r; r = (r + min) / 2; }
    }
    printf("\nBorder %d, radius %d (ratio  %f)\n[\n  ", 
	   border, r, (float)r/border);
    (void)calc_print_n(1, border, r);
    printf("\n]\n");
  }

  return 0;

}