/* plates.c Compute the number of circles in two different disk packings. Assuming we have an $w \times l$ box, how many unit disks can we pack in there assumming we have w disks on the bottom? */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or https://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #include /* how many triangular-lattice layers of radius r balls fit in height h? */ int dense_layers(double w, double h, double r) { double gap; /* distance between layers */ if ((2*r) > h) { return(0); } gap = 2.0 * r * (sqrt(3)/2.0); return(1 + floor((h - 2.0 * r) / gap)); } int plates_per_row(int row, double w, double r) { int plates_per_full_row; /* number of plates in full/even row */ plates_per_full_row = floor(w / (2 * r)); if ((row % 2) == 0) { return(plates_per_full_row); } if (((w/(2*r))-plates_per_full_row) >= 0.5) { /* odd row full, too */ return(plates_per_full_row); } else { return(plates_per_full_row - 1); } } /* How many radius r plates fit in a hexagonal-lattice packed w*h box? */ int dense_plates(double w, double l, double r) { int layers; /* number of layers of balls */ layers = dense_layers(w, l, r); return (ceil(layers/2.0) * plates_per_row(0,w,r) + floor(layers/2.0) * plates_per_row(1,w,r) ); } int grid_plates(double w, double h, double r) { int layers; /* number of layers of balls */ layers = floor(h / (2 * r)); return (layers * plates_per_row(0, w, r)); } /* Hexagonal coordinates start with the center of disk (0,0) at geometric point (0,0). The hexagonal coordinate $(xh,yh)$ refers to the center of the disk on the horizontal row xh and positive-slope diagonal yh. The geometric coordinate of such a point is a function of the radius of the disk $r$. */ void hex_to_geo(int xh, int yh, double r, double *xg, double *yg) { *yg = (2.0 * r) * xh * (sqrt(3)/2.0); *xg = (2.0 * r) * xh * (1.0/2.0) + (2.0 * r) * yh; } void geo_to_hex(double xg, double yg, double r, double *xh, double *yh) { *xh = (2.0/sqrt(3)) * yg / (2.0 * r); *yh = (xg - (2.0 * r) * (*xh) * (1.0/2.0) ) / (2.0 * r); } /* Under the hexagonal coordinate system, the set of hexagons defined by coordinates (hx,hy), where $0 <= hx <= xmax$ and $0 <= hx <= ymax$ forms a diamond-shaped patch, not a conventional axis-oriented rectangle. To solve this problem, we define array coordinates so that (ax,ay) refers to the position in an axis-oriented rectangle with (0,0) as the lower righthand point in the matrix. */ void array_to_hex(int xa, int ya, int *xh, int *yh) { *xh = xa; *yh = ya - xa + ceil(xa/2.0); } void hex_to_array(int xh, int yh, int *xa, int *ya) { *xa = xh; *ya = yh + xh - ceil(xh/2.0); } int plates_on_top(int xh, int yh, double w, double l, double r) { int number_on_top = 0; /* total plates on top */ int layers; /* number of rows in grid */ int rowlength; /* number of plates in row */ int row; /* counter */ int xla, yla, xra, yra; /* array coordinates */ layers = dense_layers(w, l, r); for (row = xh + 1; row < layers; row++) { rowlength = plates_per_row(row, w, r) - 1; hex_to_array(row, yh - (row - xh), &xla, &yla); if (yla < 0) { yla = 0; /* left boundary */ } hex_to_array(row,yh,&xra,&yra); if (yra > rowlength) { yra = rowlength; /* right boundary */ } number_on_top += yra - yla + 1; } return(number_on_top); } int main(void) { double w; /* box width */ double l; /* box length */ double r; /* plate radius */ int i; /* counters */ int xmax, ymax; printf("input box width, box length, and plate radius:\n"); scanf("%lf %lf %lf", &w, &l, &r); printf("box width=%lf, box length=%lf, and plate radius=%lf:\n", w, l, r); printf("dense packing = %d\n", dense_plates(w, l, r)); printf("grid packing = %d\n", grid_plates(w, l, r)); /* print all the possible hexes in the box */ xmax = floor(w / (2*r)); ymax = dense_layers(w,l,r); for (i = 0; i < xmax; i++) { printf("(0,%d) has %d on top.\n", i, plates_on_top(0, i, w, l, r)); } return 0; }