/* Sun Jul 4 13:15:21 JST 2004 */ /* Sun Jul 4 15:40:37 JST 2004 */ /* The height of each board is less than that of the tank, i.e. 50 cm, and differs one another. ~~~~~~~~~~~~~~~~~~~ */ #include #define min(x,y) (((x)<(y))?(x):(y)) typedef struct { int x, h; } wall_t; typedef struct { int w1, w2, b, lower[2], upper, contains; } box_t; typedef struct { int b, a; } source_t; int N, M, L, P, T; wall_t Wall[16]; box_t Box[256]; int NBox; source_t Source[16]; int NSource; double height(int x) { int i; for (i = NBox-1; i >= 0; i--) { if (Wall[Box[i].w1].x < x && x < Wall[Box[i].w2].x) { if (Box[i].contains > 0) { return (double)Box[i].b + ((double)(min(Wall[Box[i].w1].h, Wall[Box[i].w2].h) - Box[i].b) * (double)Box[i].contains / (double)capacity(i)); } } } return 0; } void topBox(int w, int *left, int *right) { int i; *left = -1; *right = -1; for (i = NBox-1; i >= 0; i--) { if (Box[i].w2 == w && *left < 0) { *left = i; } if (Box[i].w1 == w && *right < 0) { *right = i; } if (*left >= 0 && *right >= 0) { return; } } } void makeBox() { int i, y, left, right; NBox = 0; for (i = 0; i < N+1; i++) { Box[i].w1 = i; Box[i].w2 = i+1; Box[i].b = 0; Box[i].lower[0] = Box[i].lower[1] = Box[i].upper = -1; Box[i].contains = 0; NBox++; } /* The height of each board is less than that of the tank, i.e. 50 cm, */ for (y = 0; y < 50; y++) { for (i = 1; i <= N; i++) { if (Wall[i].h == y) { topBox(i, &left, &right); Box[NBox].w1 = Box[left].w1; Box[NBox].w2 = Box[right].w2; Box[NBox].b = y; Box[NBox].lower[0] = left; Box[NBox].lower[1] = right; Box[NBox].upper = -1; Box[NBox].contains = 0; Box[left].upper = NBox; Box[right].upper = NBox; NBox++; } } } } int target(int x) { int i; for (i = 0; i < NBox; i++) { if (Wall[Box[i].w1].x < x && x < Wall[Box[i].w2].x) { return i; } } } int capacity(int b) { return (Wall[Box[b].w2].x - Wall[Box[b].w1].x) * (min(Wall[Box[b].w2].h, Wall[Box[b].w1].h) - Box[b].b) * 30; } int pour_lower(int b, int left) { int i, used = 0, c; for (i = 0; i < 2; i++) { if (Box[b].lower[i] < 0) { continue; } used += pour_lower(Box[b].lower[i], left); } c = capacity(b); if (c - Box[b].contains < left - used) { used += c - Box[b].contains; Box[b].contains += c - Box[b].contains; return used; } else { Box[b].contains += left - used; used += left - used; return used; } } int pour_upper(int b, int left) { int c; left -= pour_lower(b, left); if (left <= 0) { return; } c = capacity(b); if (c - Box[b].contains < left) { left -= c - Box[b].contains; Box[b].contains += c - Box[b].contains; } else { left = 0; Box[b].contains += left; } if (Box[b].upper < 0) { return 0; } return pour_upper(Box[b].upper, left); } int main() { int i, j, k, D, DataSet; scanf("%d", &D); for (DataSet = 0; DataSet < D; DataSet++) { scanf("%d", &N); Wall[0 ].x = 0; Wall[0 ].h = 50; for (i = 1; i <= N; i++) { scanf("%d %d", &Wall[i].x, &Wall[i].h); } Wall[N+1].x = 100; Wall[N+1].h = 50; NBox = 0; makeBox(); #if 0 printf("\n----\n"); for (i = 0; i < NBox; i++) { printf("%d : Wall(%d-%d), Bottom(%d), Upper(%d), Lower(%d,%d)\n", i, Box[i].w1, Box[i].w2, Box[i].b, Box[i].upper, Box[i].lower[0], Box[i].lower[1]); } #endif scanf("%d", &M); for (i = 0; i < M; i++) { scanf("%d %d", &Source[i].b, &Source[i].a); Source[i].b = target(Source[i].b); } scanf("%d", &L); for (i = 0; i < L; i++) { scanf("%d%d", &P, &T); for (j = 0; j < NBox; j++) { Box[j].contains = 0; } for (j = 0; j < M; j++) { pour_upper(Source[j].b, Source[j].a * T); #if 0 printf("%d <== %d\n", Source[i].b, Source[j].a * T); #endif } printf("%lf\n", height(P)); #if 0 for (k = 0; k < NBox; k++) { printf("%d : Wall(%d-%d), Bottom(%d), Upper(%d), Lower(%d,%d) : Contains(%d/%d)\n", k, Box[k].w1, Box[k].w2, Box[k].b, Box[k].upper, Box[k].lower[0], Box[k].lower[1], Box[k].contains, capacity(k)); } #endif } } return 0; }