Atlantis
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24574 Accepted Submission(s): 9723

Problem Description
There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input
The 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.

Output
For 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

题目大意：
给你n对点，每对点表示一个矩阵的左下角和右上角

思路：
先无情吐槽一波，1e3+10无情wa，1100ac心都凉了，我寻思着实在找不出错误。
em。。。这是我的第一篇扫描线，经过几天的时间不断学习对扫描线也有了一点点自己的认知。

假如在直角坐标系中有这么几个矩形，现在要你求它的面积（重复的面积只计算一次）
那么扫描线的核心就是：
先把所有矩形的边形成一条线

然后我们用线段树维护所有扫描线的当前最宽度
那么首先需要建树，这里和以往的建树有一点点不同，以往线段树叶子节点表示一个单点，但是这里的叶子节点，假如[1,1]，表示[1,2]这个区间，类似的其他的区间也都是[x,y]->[x,y+1]。

上面的四个点划分出来三个区间，我们用线段树取维护这个区间而不是去维护这个点。
上述题目中的宽是浮点数，所以范围表示可能会比较大，所以需要离散化一下。
然后我们对线段的高度升序，然后一条一条去扫描，这里需要一个比较重要的变量id，每个矩形的下面那条边称为下位边，用1，上面那条称为上位边，用-1表示。用这个标记可以实现区间更新，不错的性能。
em。。。。具体看代码把。
另外附上一个我学习的博客：

https://blog.csdn.net/xianpingping/article/details/83032798

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=1100;
struct node{
	double x,y,h;
	int id;
	node(){}
	node(double a,double b,double c,int d):x(a),y(b),h(c),id(d){}
	bool operator <(const node &rhs)const{
		return h<rhs.h;
	}
}seg[maxn];
struct Node{
	double sum;
	int id;
	int l,r;
}Node[maxn];
double _hash[maxn];
void build(int l,int r,int i){
	Node[i].l=l;
	Node[i].r=r;
	Node[i].id=0;
	Node[i].sum=0;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(l,mid,i<<1);
	build(mid+1,r,i<<1|1); 
}
void pushup(int i){
	if(Node[i].id){
		Node[i].sum=_hash[Node[i].r+1]-_hash[Node[i].l]; 
	}else{
		Node[i].sum=Node[i<<1|1].sum+Node[i<<1].sum;
	}
}
void update(int i,int d,int l,int r){
	if(Node[i].l==l&&Node[i].r==r){
		Node[i].id+=d;
		pushup(i);
		return ;
	}
	int mid=(Node[i].l+Node[i].r)>>1;
	if(r<=mid){
		update(i<<1,d,l,r);
	}else if(l>mid){
		update(i<<1|1,d,l,r);
	}else{
		update(i<<1,d,l,mid);
		update(i<<1|1,d,mid+1,r);
	}
	pushup(i);
}
int main(){
	int q;int ca=1;
	while(scanf("%d",&q)&&q){
		int n=1,m=1;
		for(int i=0;i<q;i++){
			double x1,y1,x2,y2;
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			seg[n++]=node(x1,x2,y1,1);
			seg[n++]=node(x1,x2,y2,-1);
			_hash[m++]=x1;
			_hash[m++]=x2;
		}
		sort(seg+1,seg+n);
		sort(_hash+1,_hash+m);
		int k=unique(_hash+1,_hash+m)-(_hash+1);
		build(1,k-1,1);
		double ans=0.0;
		for(int i=1;i<n;i++){
			int l=lower_bound(_hash+1,_hash+k,seg[i].x)-_hash;
			int r=lower_bound(_hash+1,_hash+k,seg[i].y)-_hash;
			r--;
			if(l<=r){
				update(1,seg[i].id,l,r);
			}
			ans+=(seg[i+1].h-seg[i].h)*Node[1].sum;
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n",ca++,ans); 
	}
}