有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。
其中一些甚至包括岛屿部分地图。
但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。
您的朋友 Bill 必须知道地图的总面积。
你自告奋勇写了一个计算这个总面积的程序。
输入格式
输入包含多组测试用例。
对于每组测试用例，第一行包含整数?nn，表示总的地图数量。
接下来?nn?行，描绘了每张地图，每行包含四个数字?x1,y1,x2,y2x1,y1,x2,y2（不一定是整数），(x1,y1)(x1,y1)?和?(x2,y2)(x2,y2)?分别是地图的左上角位置和右下角位置。
注意，坐标轴?xx?轴从上向下延伸，yy?轴从左向右延伸。
当输入用例?n=0n=0?时，表示输入终止，该用例无需处理。
输出格式
每组测试用例输出两行。
第一行输出?Test case #k，其中?kk?是测试用例的编号，从?11?开始。
第二行输出?Total explored area: a，其中?aa?是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。
在每个测试用例后输出一个空行。
数据范围
1≤n≤100001≤n≤10000,
0≤x1<x2≤1000000≤x1<x2≤100000,
0≤y1<y2≤1000000≤y1<y2≤100000
注意，本题?nn?的范围上限加强至?1000010000。
输入样例：
2
10 10 20 20
15 15 25 25.5
0
输出样例：
Test case #1
Total explored area: 180.00
/*感觉这要没有特殊区间查询，lz标记就不用下放，lz标记用法是真的多*/
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
vector<double > vs;/*从下往上扫描*/
struct line/*用来存直线：把每个矩形的上边跟下边都存成一条条线段*/
{
double x,y1,y2;/*x是直线的高度,y1,y2是左右端点*/
int f;/*1表示下边，表示这条边要开始加入，-1结束*/
bool operator < (const line &t) const
{
return x<t.x;
}
} seg[200100];
struct segtree
{
int l,r,lz;
double len;
} tree[201000];
int find(double x)
{
return lower_bound(vs.begin(),vs.end(),x)-vs.begin();
}
void build(int node,int l,int r)
{
int mid;
tree[node]= {l,r,0,0};
if(l==r)
return;
mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
}
void up(int node)
{
if(tree[node].lz)
{
tree[node].len=vs[tree[node].r+1]-vs[tree[node].l];/*当lz！=0那么这条线段还要积分使用*/
return;
}
tree[node].len=tree[node*2].len+tree[node*2+1].len;/*向上级汇报下面一共覆盖的区间长度*/
}
void update(int node,int l,int r,int z)/*主要是求将线段加入或删除，再求总区间覆盖长度*/
{
if(tree[node].l>=l&&tree[node].r<=r)
{
tree[node].lz+=z;/*lz的作用：记录这段区间被覆盖了多少次，一段线段被删除后
还可能有其他线段在这段区间上的积分没有结束，即当lz！=0那么这条线段还要积分使用*/
up(node);
return;
}
int mid=(tree[node].l+tree[node].r)/2;
if(l<=mid) update(node*2,l,r,z);
if(r>=mid+1) update(node*2+1,l,r,z);
up(node);
}
int main()
{
int n,m,j,i,L,R,k=0,zz=1;
double x1,x2,y1,y2,sum=0.0;
while(~scanf("%d",&n)&&n)
{
vs.clear();
k=0;
for(i=1; i<=n; i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
seg[++k]= {x1,y1,y2,1};
seg[++k]= {x2,y1,y2,-1};
vs.push_back(y1);
vs.push_back(y2);
}
sort(seg+1,seg+1+k);/*为了从低到高扫描*/
sort(vs.begin(),vs.end());
vs.erase(unique(vs.begin(),vs.end()),vs.end());/*对所有的线段的左右端点进行离散查重*/
m=vs.size();/*把 15 20 25 25.5 离散化成 0 1 2 3 区间长度就是vs[3]-vs[0]*/
build(1,0,m-2);
/*建树区间0~(m-2)主要是想用[l,r]要表示区间[l,r+1],因为线段
长度都是大于0的[3,3]区间是没有意义的*/
update(1,find(seg[1].y1),find(seg[1].y2)-1,seg[1].f);
sum=0;
for(i=2; i<=k; i++)
{
L=find(seg[i].y1);/*找到这条线段对应的高度在离散数组中对应的下标*/
R=find(seg[i].y2)-1;
sum+=tree[1].len*(seg[i].x-seg[i-1].x);
update(1,L,R,seg[i].f);/*就是算seg[i-1]~seg[i]参加积分的线段长度有一共有多长*/
}
printf("Test case #%d\n",zz++);
printf("Total explored area: %.2lf\n\n",sum);
}
return 0;
}