/*
* 最近在看线段树放面的资料，好像蛮简单的
* 可是当写代码的时候还是发现了许多的问题，一下代码
* 还没有测试过，因为我还没有找到足够简单的题目来
* 测试这个程序。ft, 终于过了，昨晚WA了许多次原来是因为少输出了一个
回车，ft他竟给了我一个WA，让我调了很长时间．
回车，ft他竟给了我一个WA，让我调了很长时间．
* 比起字典树和并查集，这个代码实现起来要复杂很多。。。
* http://acm.zju.edu.cn/show_problem.php?pid=1128
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INSERT 1
#define DELETE -1
struct segtree {
struct segtree *lchild;
struct segtree *rchild;
double left, right;
double m; // 侧度
int count; // 覆盖该区间的线段条数
int line; // 区间中互不相交的线段的数量
int lbd, rbd; // 表示左右端点是否被覆盖到
int lw, hi; // 线段的区间
};
struct segtree *initree(double Y[], int lw, int hi)
{
struct segtree *root;
if (lw >= hi) return NULL;
root = (struct segtree *)malloc(sizeof(struct segtree));
if (hi - lw == 1) {
root->lchild = root->rchild = NULL;
} else {
root->lchild = initree(Y, lw, (lw + hi)/2);
root->rchild = initree(Y, (lw + hi)/2, hi);
}
root->m = 0;
root->count = root->line = 0;
root->lbd = root->rbd = 0;
root->lw = lw;
root->hi = hi;
root->left = Y[lw];
root->right = Y[hi];
return root;
}
void add(int &v, int b)
{
v += b;
if (v < 0) v = 0;
}
// we can sure [lw, hi] in the section root...
void update(struct segtree *root, double lw, double hi, int flag)
{
// 分为叶节点和非叶节点
if (root->lchild && root->rchild) {
if (hi <= root->rchild->left) update(root->lchild, lw, hi, flag);
else {
if (lw >= root->rchild->left) {
update(root->rchild, lw, hi, flag);
} else {
update(root->lchild, lw, root->lchild->right, flag);
update(root->rchild, root->rchild->left, hi, flag);
}
}
if (root->left == lw && root->right == hi) add(root->count, flag);
if (root->left == lw) add(root->lbd, flag);
if (root->right == hi) add(root->rbd, flag);
if (root->count > 0) {
root->line = 1;
root->m = root->right - root->left;
} else {
root->m = root->lchild->m + root->rchild->m;
root->line = root->lchild->line + root->rchild->line;
if (root->lchild->rbd && root->rchild->lbd) root->line--;
}
} else if (root->left == lw && root->right == hi) {
// 在叶节点进行删除
add(root->count, flag);
add(root->lbd, flag);
add(root->rbd, flag);
if (root->count == 0) {
root->m = 0;
root->line = 0;
} else {
root->m = root->right - root->left;
root->line = 1;
}
}
}
void insert(struct segtree *root, double lw, double hi)
{
update(root, lw, hi, INSERT);
}
void del(struct segtree *root, double lw, double hi)
{
update(root, lw, hi, DELETE);
}
void destroy(struct segtree *root)
{
if (root->lchild) destroy(root->lchild);
if (root->rchild) destroy(root->rchild);
free(root);
}
// the test routine...
struct env {
double x, y1, y2;
int flag; // INSERT or DELETE...
} env[201];
double Y[201];
int n;
int cmp1(const void *a, const void *b)
{
const double *s1 = (const double *)a;
const double *s2 = (const double *)b;
if (*s1 > *s2) return 1;
return -1;
}
int cmp2(const void *a, const void *b)
{
const struct env *s1 = (const struct env *)a;
const struct env *s2 = (const struct env *)b;
if (s1->x > s2->x) return 1;
return -1;
}
int main(void)
{
double x1, y1, x2, y2, area;
struct segtree *root;
int i, cas = 0;
while (scanf("%d", &n) == 1 && n) {
for (i = 0; i < 2*n; i += 2) {
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
Y[i] = y1;
Y[i + 1] = y2;
env[i].flag = INSERT;
env[i + 1].flag = DELETE;
env[i].x = x1;
env[i + 1].x = x2;
env[i + 1].y1 = env[i].y1 = y1;
env[i + 1].y2 = env[i].y2 = y2;
}
qsort(Y, 2*n, sizeof(double), cmp1);
qsort(env, 2*n, sizeof(struct env), cmp2);
root = initree(Y, 0, 2*n - 1);
update(root, env[0].y1, env[0].y2, env[0].flag);
for (i = 1, area = 0; i < 2*n; i++) {
area = area + root->m * (env[i].x - env[i - 1].x);
update(root, env[i].y1, env[i].y2, env[i].flag);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++cas, area);
destroy(root);
}
return 0;
}