/*
*
* 扫描线算法,把y轴上的边切割成线段,利用线段树统计每一个出现过的x位置上,所有累计覆盖次数
* 大于0的线段的总长度和,每个线段树节点维护线段区间中所有线段被完整覆盖的次数以及所有计数
* 值大于0的线段的总长度和,不需要懒标记,这个题目懒标记和维护的两个字段之间没有什么必然联系
* 加上懒标记反而难搞了
* 值得注意的是每一个区间的完全覆盖计数不可能减到0以下,如果更新区间覆盖
* 计数时候,当前要更新的区间范围刚好和节点表示的区间范围一样,只可能出现
* 两种情况:
* 情况1. 当前是在增加计数,那当前这个待更新的区间中的所有线段的计数值必然会在更新后大于等于1
* 这样整个区间合法的线段总和就是这个区间所有线段的长度和,用提前预处理出来的前缀和来算
*
* 情况2. 当前在减少计数,如果当前区间的覆盖计数减少后仍然大于0,那当前区间里面所有线段都还是
* 合法的,当前区间的合法线段总和还是区间中所有线段的长度和,如果计数减少后区间的完全覆盖次数
* 变成0了,那当前区间的合法线段和,就是两个子区间的合法线段和的总和
*
* 这个题目的特殊点在于,所有区间一定是增加计数和删除计数成对出现,一个区间的覆盖计数肯定是整体
* 全部增加或者全部减少,不可能出现子区间去增加或者减少,所以区间的完全覆盖计数是不必向子区间
* 传递的,如果传递下去,当初增加这个计数的区间被删掉的时候,又要每个子区间去减一遍,浪费时间,
* 不如就把增量放到父节点,不往下传,减的时候就把父节点增量删掉,最后结果是一样的,就可以免除
* 不必要的递归
*
*
*/
#include <stdio.h>
#include <set>
#include <map>
#include <vector>
using namespace std;
struct Data {
double sum; // 所有被矩形边覆盖的线段的总长度
long long overlap_cnt; // 区间被完整覆盖的次数
};
struct Node {
int start; // 区间开始位置
int end; // 区间结束位置
Data data; // 区间数据
}__global_nodes[100005*4] ;
class SegmentTree {
private:
Node* __nodes; // 节点数组
int __n; // 区间为0到n-1
vector<double> edge_prefix_sum; // 边长的前缀和
vector<double>& idx2elen;
// 更新区间数据
void __update_range(int node_idx, int start, int end, long long val) {
Node& node = __nodes[node_idx];
if (node.start == start and node.end == end) {
node.data.overlap_cnt += val;
if (node.data.overlap_cnt > 0) {
node.data.sum = node.start == 0 ? edge_prefix_sum[node.end] : edge_prefix_sum[node.end] - edge_prefix_sum[node.start-1];
} else {
node.data.sum = __nodes[node_idx*2+1].data.sum + __nodes[node_idx*2+2].data.sum;
}
return;
}
int mid = (node.start + node.end) >> 1;
if (end <= mid) {
__update_range(node_idx*2+1, start, end, val);
} else if (start >= mid + 1) {
__update_range(node_idx*2+2, start, end, val);
} else {
__update_range(node_idx*2+1, start, mid, val);
__update_range(node_idx*2+2, mid+1, end, val);
}
if (node.data.overlap_cnt == 0) {
node.data.sum = __nodes[node_idx * 2 + 1].data.sum + __nodes[node_idx * 2 + 2].data.sum;
}
}
// 获取区间统计信息
double __get_val(int node_idx, int start, int end) {
Node& node = __nodes[node_idx];
if (node.start == start && node.end == end) {
return node.data.sum;
}
int mid = (node.start + node.end) >> 1;
if (end <= mid) {
return __get_val(node_idx*2+1, start, end);
} else if (start >= mid+1) {
return __get_val(node_idx*2+2, start, end);
} else {
double val1 = __get_val(node_idx*2+1, start, mid);
double val2 = __get_val(node_idx*2+2, mid+1, end);
return val1 + val2;
}
}
public:
SegmentTree(int n, Node* pnodes, vector<double>& idx2edge_len) : idx2elen(idx2edge_len) {
__n = n;
__nodes = pnodes;
__nodes[0] = {0, n-1, 0};
for (int i = 0; i < __n << 2; i++) {
if (__nodes[i].start == __nodes[i].end and __nodes[i].end == __n-1) {
break;
}
int mid = (__nodes[i].start + __nodes[i].end) / 2;
__nodes[i*2+1] = {__nodes[i].start, mid, {0.0, 0,}};
__nodes[i*2+2] = {mid+1, __nodes[i].end, {0.0, 0,}};
}
// 计算边长的前缀和
edge_prefix_sum.push_back(idx2elen[0]);
for (int i = 1; i < idx2elen.size(); i++) {
edge_prefix_sum.push_back(idx2elen[i] + edge_prefix_sum[i-1]);
}
}
// 更新区间数据接口
void update_range(int start, int end, long long val) {
__update_range(0, start, end, val);
}
// 获取区间统计数据接口
double get_val(int start, int end) {
return __get_val(0, start, end);
}
};
bool flag = false;
int main(void) {
//freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);
int n;
int case_cnt = 1;
while (true) {
scanf("%d", &n);
double x1, y1, x2, y2;
if (n == 0) {
break;
}
set<double> x_set, y_set;
map< double, vector<pair<double, double>> > x2line_add; // 增加的边
map< double, vector<pair<double, double>> > x2line_sub; // 减少的边
for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
x_set.insert(x1);
x_set.insert(x2);
y_set.insert(y1);
y_set.insert(y2);
x2line_add[x1].push_back(pair<double, double>(y1, y2));
x2line_sub[x2].push_back(pair<double, double>(y1, y2));
}
map<double, int> y2idx; // y坐标到点序号的映射
vector<double> idx2eddge_len; // 边的编号到边长度的映射
int idx = 0;
double last_val = -1.0;
for (auto y_val : y_set) {
y2idx[y_val] = idx++;
if (last_val != -1.0) {
idx2eddge_len.push_back(y_val - last_val);
}
last_val = y_val;
}
SegmentTree tree(idx2eddge_len.size(), __global_nodes, idx2eddge_len);
double last_x = -1.0;
double total_area = 0.0;
for (double x_val : x_set) {
double total_edge_len = tree.get_val(0, idx2eddge_len.size()-1);
if (last_x != -1.0) {
total_area += total_edge_len * (x_val - last_x);
}
last_x = x_val;
for (auto& p : x2line_add[x_val]) {
int start = y2idx[p.first];
int end = y2idx[p.second];
if (end-1 >= start) {
tree.update_range(start, end-1, 1);
}
}
for (auto& p : x2line_sub[x_val]) {
int start = y2idx[p.first];
int end = y2idx[p.second];
if (end-1 >= start) {
tree.update_range(start, end-1, -1);
}
}
}
printf("Test case #%d\nTotal explored area: %.2lf\n", case_cnt++, total_area);
printf("\n");
}
return 0;
}