Write a program to calculate the damage of a bomb explosion. We assume that when a bomb explodes, it will create an N by N square explosion around its center. In addition, an N by N explosion will create four smaller N/2 by N/2 explosions around its boundary. The four new explosions will be next to the original explosion, and align with the original explosion at the midpoints of the four sides. Please refer to the following figure for an illustration. This "chain-reaction" explosion will stop when the size of explosion is no more than 2. Explosion causes damage. If a location (x, y) is within or at the boundary of an N by N explosion, it will sustain N damage. If a location (x, y) is within multiple explosions, the total damage of this location is the sum of damage from individual explosions. An area is a collection of locations that form a rectangle. For example, an 1 by 2 area with lower-left corner at (0, 0) consist of locations (0, 0), (1, 0), (0, 1), (1, 1), (0, 2), and (1, 2). The damage of an area is the sum of the damage of its locations. Now given the center of the original explosion (X, Y) and it size N, and an area with lower-left corner (x, y), width w and height h, compute the total damage of this area.
The input has the following integers -- X, Y, N, x, y, w, h. It is guaranteed that N is a power of 2 and all input numbers will fit in signed 32-bit integer.
The total damage of the given area which always fits in signed 32-bit integer.
##Sample Input:
0 0 16 -100 -100 200 200
0 0 16 -8 -8 16 16
##Sample Output(Mon.):
7680
4448
##Sample Output(Wed.)
9968
5600
##分析 星期一是在計算爆炸區塊與目標區塊交集的 面積 。 星期三是在累計目標區塊內的每個 點 。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int min(int a, int b) {
return ((a < b) ? a : b);
}
int max(int a, int b) {
return ((a < b) ? b : a);
}
int bomb(int X, int Y, int N, int x, int y, int w, int h) {
/* if (N*N <= 2) return 0;
To prevent overflow, we won't use N*N
since N is int, N > 0 => if (N <= 1) */
if (N <= 1) return 0;
int r = N / 2;
int total = 0;
/* current explosion from (X-r, Y-r) to (X+r, Y+r) */
/* find intersection of Rect(X-r, Y-r, X+r, Y+r) and Rect(x, y, x+w, y+h) */
int iw = max(0, min(X+r, x+w) - max(X-r, x));
int ih = max(0, min(Y+r, y+h) - max(Y-r, y));
int area = iw*ih;
total += area*N;
/* chain explosions */
total += bomb(X-r-r/2, Y, N/2, x, y, w, h);
total += bomb(X+r+r/2, Y, N/2, x, y, w, h);
total += bomb(X, Y-r-r/2, N/2, x, y, w, h);
total += bomb(X, Y+r+r/2, N/2, x, y, w, h);
return total;
}
int main() {
int X, Y, N, x, y, w, h;
while (scanf("%d %d %d %d %d %d %d", &X, &Y, &N, &x, &y, &w, &h) != EOF) {
printf("%d\n", bomb(X, Y, N, x, y, w, h));
}
return 0;
}#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int min(int a, int b) {
return ((a < b) ? a : b);
}
int max(int a, int b) {
return ((a < b) ? b : a);
}
int bomb(int X, int Y, int N, int x, int y, int w, int h) {
/* if (N*N <= 2) return 0;
To prevent overflow, we won't use N*N
since N is int, N > 0 => if (N <= 1) */
if (N <= 1) return 0;
int r = N / 2;
int total = 0;
/* current explosion from (X-r, Y-r) to (X+r, Y+r) */
/* less effecient way
for (int i=X-r; i<=X+r; i++)
for (int j=Y-r; j<=Y+r; j++)
if (x <= i && i <= x+w && y <= j && j <= y+h)
total += N;
*/
int iw, ih;
if (x+w < X-r || X+r < x)
iw = 0;
else
iw = min(X+r, x+w) - max(X-r, x) + 1;
if (y+h < Y-r || Y+r < y)
ih = 0;
else
ih = min(Y+r, y+h) - max(Y-r, y) + 1;
total += iw*ih*N;
/* chain explosions */
total += bomb(X-r-r/2, Y, N/2, x, y, w, h);
total += bomb(X+r+r/2, Y, N/2, x, y, w, h);
total += bomb(X, Y-r-r/2, N/2, x, y, w, h);
total += bomb(X, Y+r+r/2, N/2, x, y, w, h);
return total;
}
int main() {
int X, Y, N, x, y, w, h;
while (scanf("%d %d %d %d %d %d %d", &X, &Y, &N, &x, &y, &w, &h) != EOF) {
printf("%d\n", bomb(X, Y, N, x, y, w, h));
}
return 0;
}