/* 1997 East-Central ACM regional programming contest Held on November 8, 1997 Doing Windows -- Problem 5 Sample solution by Ed Karrels, Ed@tool.com November 1997 */ #include #include int sc_w, sc_h; // width & height of screen double win_ratio[4]; // width/height ratio of each window // assume nonzero width and nonzero height /* Given the width of the window, compute the height based on the width/height ratio. If it doesn't work out to an integer (give it a .000001 fudge factor to account for roundoff error), return -1; */ int try_width(int win_no, int width) { if (width == 0) return -1; double height = width / win_ratio[win_no]; int int_height = height + .0000005; if (fabs(height-int_height) < .000001) { return int_height; } else { return -1; } } /* Same deal, but with height to weight. */ int try_height(int win_no, int height) { if (height == 0) return -1; double width = height * win_ratio[win_no]; int int_width = width + .0000005; if (fabs(width-int_width) < .000001) { return int_width; } else { return -1; } } /* Try recursively filling up the sides of the screen. For example: +------------+ |111111111111| | | | | | | | | | | +------------+ +------------+ |111111111111| |2222 | |2222 | |2222 | |2222 | |2222 | +------------+ +------------+ |111111111111| |222233333333| |222233333333| |222233333333| |2222 | |2222 | +------------+ +------------+ |111111111111| |222233333333| |222233333333| |222233333333| |222244444444| |222244444444| +------------+ sc_w, sc_h - remaining size of the screen used[] - 1/0 flag, noting which windows have already been placed n - # of levels placed so far */ int try_filling(int sc_w, int sc_h, int used[], int n) { int win_no, wd, ht; // if the screen is full and all 4 windows have been // placed, we're good. If not all 4 windows have been // placed, we've run out of room. if (sc_w == 0 || sc_h == 0) { return (n == 4) ? 1 : 0; } // Try each of the 4 windows, checking that we're not // using a windows that's already been placed. for (win_no=0; win_no<4; win_no++) { if (!used[win_no]) { used[win_no] = 1; // try filling up the top of the screen, thus // the full width of the screen ht = try_width(win_no, sc_w); if (ht != -1 && ht <= sc_h) { // if this height works and does not overflow // the screen, try placing the rest of the windows if (try_filling(sc_w, sc_h - ht, used, n+1)) return 1; } else { // try filling the side of the screen wd = try_height(win_no, sc_h); if (wd != -1 && wd <= sc_w) { if (try_filling(sc_w - wd, sc_h, used, n+1)) return 1; } } used[win_no] = 0; } } return 0; } /* Try filling up the screen this way: +---+--------+ | | | +---+---+----| | | | | | | | | | | | | +-------+----+ Specifically, find two windows to fill the top, with the combined width equal to the width of the screen and having the same height. Then do the same for the bottom. This requires a little algebra: Hn = height of window n Wn = width of window n w = screen width Rn = width/height ratio of window n R1 = W1/H1 R2 = W2/H2 H1 = H2 W1 + W2 = w H1 = H2 -> W1/R1 = W2/R2 -> W1/R1 = (w - W1)/R2 -> W1 = (R1 * w)/(R1 + R2) */ int try_mixed() { int w1, w2, w3, w4; int used[4] = {0}; for (w1=0; w1<1; w1++) { used[w1] = 1; for (w2=0; w2<4; w2++) { if (!used[w2]) { used[w2] = 1; // fit the first two windows to the top int width_1 = (win_ratio[w1] * sc_w) / (win_ratio[w1] + win_ratio[w2]); int height_1 = try_width(w1, width_1); int width_2 = sc_w - width_1; int height_2 = try_width(w2, width_2); if (height_1 != -1 && height_1 == height_2) { for (w3=0; w3<4; w3++) { if (!used[w3]) { used[w3] = 1; for (w4=0; w4<4; w4++) { if (!used[w4]) { // fit the last two windows to the bottom int width_3 = (win_ratio[w3] * sc_w) / (win_ratio[w3] + win_ratio[w4]); int height_3 = try_width(w3, width_3); int width_4 = sc_w - width_3; int height_4 = try_width(w4, width_4); if (height_3 != -1 && height_3 == height_4 && height_1 + height_3 == sc_h) return 1; } } used[w3] = 0; } } } used[w2] = 0; } } used[w1] = 0; } return 0; } int main() { int i, set_no = 1, found, w, h; // FILE *inf = fopen("prob_5.in", "r"); FILE *inf = stdin; int used[4]; while (fscanf(inf, "%d %d", &sc_w, &sc_h), sc_w || sc_h) { found = 0; for (i=0; i<4; i++) { used[i] = 0; fscanf(inf, "%d %d", &w, &h); win_ratio[i] = (float)w / h; } // try filling up the screen one full side at a time if (try_filling(sc_w, sc_h, used, 0)) { found = 1; } else { // try alternate filling scheme if (try_mixed()) { found = 1; } else { // OK, that didn't work. Try flipping horizontal // an vertical dimensions. for (i=0; i<4; i++) win_ratio[i] = 1 / win_ratio[i]; w = sc_w; sc_w = sc_h; sc_h = w; if (try_mixed()) { found = 1; } } } if (found) { printf("Set %d: Yes\n", set_no++); } else { printf("Set %d: No\n", set_no++); } } return 0; }