From given size of area and rect, examine maximum number of rects can be contained in the area, and print its pattern.

fillrect.c

/* From given size of area and rect, examine maximum number of rects can be 
   contained in the area, and print its pattern.
   ( answer for a programming question at http://q.hatena.ne.jp/1245118420 )
*/
#include <stdlib.h>
#include <stdio.h>

int do_num_contain_rect(int aw, int ah, int w, int h)
{
  if (w>aw || h>ah) return 0;
  
  int n = (aw/w) * (ah/h); /* number of rects can be placed in left top area */
  int rw = aw%w; /* width of available space on right side */
  int bh = ah%h; /* height of available space on bottom side */
  int nl = 0; /* number of rect can be contained in left space */
  if (rw>=h && w<=ah) { /* right side is available */
    nl = (rw/h) * (ah/w);
  } else if (bh>=w && h<=aw) { /* bottom side is available */
    nl = (bh/w) * (aw/h);
  }
  return n+nl;
}

int print_contain_rect(int aw, int ah, int w, int h) 
{
  const char * rect_format = "%4d: (%4d, %4d) - (%4d, %4d)\n";
  
  int x, y, n;
  int rw = aw%w; /* width of available space on right side */
  int bh = ah%h; /* height of available space on bottom side */
  for (y=0,n=0; y<ah-h+1; y+=h) {
    for (x=0; x<aw-w+1; x+=w,n++) {
      printf(rect_format, n, x, y, x+w-1, y+h-1);
    }
  }

  if (rw>=h && w<=ah) { /* right side is available */
    puts("(fill right side)");
    for (y=0; y<ah-w+1; y+=w) {
      for (; x<aw-h+1; x+=h,n++) {
        printf(rect_format, n, x, y, x+h-1, y+w-1);
      }
    }
  } else if (bh>=w && h<=aw) { /* bottom side is available */
    puts("(fill bottom side)");
    for (; y<ah-w+1; y+=w) {
      for (x=0; x<aw-h+1; x+=h,n++) {
        printf(rect_format, n, x, y, x+h-1, y+w-1);
      }
    }
  }
  printf("%d rects are placed\n", n);
  return 0;
}

int num_contain_rect(int aw, int ah, int w, int h)
{
  int n1 = do_num_contain_rect(aw, ah, w, h);
  int n2;
  printf("given side: %d rects\n", n1);
  if (w!=h) {
    n2 = do_num_contain_rect(aw, ah, h, w); /* test reverse side */
    printf("reverse side: %d rects\n", n2);
  } else {
    n2=n1;
  }

  if (w!=h && n1==n2) {
    puts("accept both side");
    puts("");
    puts("pattern A:");
    print_contain_rect(aw, ah, w, h);
    puts("");
    puts("pattern B:");
    print_contain_rect(aw, ah, h, w);
    return n1;
  } else if (n1<n2) {
    puts("accept reverse side");
    print_contain_rect(aw, ah, h, w);
    return n2;
  } else {
    puts("accept given side");
    print_contain_rect(aw, ah, w, h);
    return n1;
  }
}

int main(int argc, char *argv[])
{
  if (argc < 5) {
    printf("usage: %s area_width area_height rect_width rect_height\n",
           argv[0]);
    return -1;
  }
  int aw = atoi(argv[1]);
  int ah = atoi(argv[2]);
  int w = atoi(argv[3]);
  int h = atoi(argv[4]);
  num_contain_rect(aw, ah, w, h);
  return 0;
}