InputThe input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1<x2<=100000;0<=y1<y2<=100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don’t process it.OutputFor each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.
Output a blank line after each test case.
Sample Input
2
10 10 20 20
15 15 25 25.5
0
Sample Output
Test case #1
Total explored area: 180.00 这题也是模板提
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
#define bug printf("******\n");
#define rtl rt<<1
#define rtr rt<<1|1
typedef long long LL;
const int maxn = 1e5 + ;
struct LINE {
double x, y1, y2;
int flag;
} line[];
int cmp(LINE a, LINE b) {
return a.x < b.x;
}
struct node {
double pre, l, r;
int cover, flag;
} tree[];
double y[];
void build(int rt, int l, int r) {
tree[rt].l = y[l], tree[rt].r = y[r];
tree[rt].flag = -, tree[rt].cover = , tree[rt].pre = -;
if (l + == r) {
tree[rt].flag = ;
return ;
}
int m = (l + r) >> ;
build(rtl, l, m);
build(rtr, m, r);
}
double query(int rt, double x, double y1, double y2, int flag) {
if (tree[rt].r <= y1 || tree[rt].l >= y2) return ;
if (tree[rt].flag == ) {
if (tree[rt].cover > ) {
double pre = tree[rt].pre;
double ans = (x - pre) * (tree[rt].r - tree[rt].l);
tree[rt].pre = x;
tree[rt].cover += flag;
return ans;
} else {
tree[rt].cover += flag;
tree[rt].pre = x;
return ;
}
}
return query(rtl, x, y1, y2, flag) + query(rtr, x, y1, y2, flag);
}
int main() {
int cas = , n;
while(scanf("%d", &n), n) {
int cnt = -;
for (int i = ; i < n ; i++) {
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
y[++cnt] = y1;
line[cnt].flag = ;
line[cnt].x = x1;
line[cnt].y1 = y1;
line[cnt].y2 = y2;
y[++cnt] = y2;
line[cnt].flag = -;
line[cnt].x = x2;
line[cnt].y1 = y1;
line[cnt].y2 = y2;
}
sort(y, y + cnt + );
sort(line, line + cnt + , cmp);
build(, , cnt);
double ans = ;
for (int i = ; i <= cnt ; i++ )
ans += query(, line[i].x, line[i].y1, line[i].y2, line[i].flag);
printf("Test case #%d\n", cas++);
printf("Total explored area: %.2lf\n\n", ans);
}
return ;
}