[UVA][幾何、交集] 11639 - Guard the Land
Problem D
Guard the Land
Input: Standard Input
Output: Standard Output
Farmer Latif has a rectangular shaped land of 100 meter width and 100 meter height. Any point in this land can be defined as (x, y) where x is the distance of the point from left side of the land and y is the distance of the point from bottom side. So lower left corner of the land is (0, 0) and upper right corner of the land is (100, 100).
Every night Latif hires two guards to guard his crop in the land. A guard can guard a rectangular shaped region. Any guard has some limitation of area to guard. The guard might not be able to guard the whole land. So every night Latif defines two rectangular regions for two guards to be guarded by them. The sides of this rectangular region are parallel to the sides of the Latif’s land. He defines the region for guards by four integers x1, y1, x2, y2. Here (x1, y1) is the lower left corner of the region and (x2, y2) is the upper right corner of the region.
The region which is guarded by two guards is considered strongly secured, the region which is guarded by exactly one guard is weakly secured, and the region which is guarded by no guard is unsecured.
In this problem, you have to find
the area of strongly secured region, weakly secured region and unsecured region
in 
for every
night.
Input
Input will start with a line
having a positive integer N(
), the number of nights Latif hires guards.
For each of the N nights, there are two lines in input, first one defines the
region of first guard and the second one defines the region of second guard.
Each of this line will contain four integers x1, y1, x2, y2 (
).
Output
For each land you have to output one line, giving the night number followed by three integers: Area of strongly secured region, area of weakly secured region and area of unsecured region of Latif’s land. See sample output for exact format.
Sample Input Output for Sample Input
|
2 10 10 20 20 15 15 25 25 10 10 20 20 20 20 30 30 |
Night 1: 25 150 9825 Night 2: 0 200 9800 |
The picture above depicts the first sample input
#include <stdio.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
typedef struct {
int x, y;
} Pt;
int main() {
int t, cases = 0;
scanf("%d", &t);
while(t--) {
Pt a, b, c, d;
int i, j, k, l;
scanf("%d %d %d %d", &a.x, &a.y, &b.x, &b.y);
scanf("%d %d %d %d", &c.x, &c.y, &d.x, &d.y);
i = max(a.x, c.x), j = max(a.y, c.y);
k = min(b.x, d.x), l = min(b.y, d.y);
int A = (b.x-a.x)*(b.y-a.y);
int B = (d.x-c.x)*(d.y-c.y);
int C = (i-k)*(j-l);
printf("Night %d: ", ++cases);
if(i >= k || j >= l) {
printf("0 %d %d\n", A+B, 10000-A-B);
} else {
printf("%d %d %d\n", C, A+B-C-C, 10000-A-B+C);
}
}
return 0;
}