hdu 1542 Atlantis (线段树+扫描线求矩形面积并，模板题)
题意：
求n(100)个矩形的面积并。
思路：
扫描线+线段树
题目是2000年中欧区域赛的题目，虽然年代久远，但是有好几个点还是很值得学习的。
首先是离散化的适用范围:
之前比较常用的是将比较大的整数值离散化，常常是因为数值太大无法作为下标。
那么其实，浮点数有的时候也需要进行离散化，比如作为数组的下标，比如用来枚举。
做法上是和将较大的整数值离散化没有区别，因为遇到的题目不多，所以特意记录一下。
第二点是扫描线的思想：
其实扫描线的思想很早就接触过，noip2011的时候，tyvj上有一道类似的题目，不过是一唯的，当时印象深刻的是@Ocean 兄的那个比喻：
一段公路上右很多区间要收不同的费用，区间的开始给一个标记，表示该段区间对答案有贡献，区间的结束拿走该标记，表示该段区间对答案的贡献结束。
这就是扫描线的思想。
第三个是处理线段覆盖问题的一般做法：
通常线段树的节点处理的都是点，处理线段的时候就会比较麻烦。
另外很重要的一点就是， 线段树都是维护一个点集， 但是对于边的问题就会变得很麻烦， 我们可以按照区间左端点建立线段树， 那么一个点表示的就不是点了， 而是起点在这个点的一个线段。 这**样的话， 右区间就要相应的-1， 例如更新区间[1, 4]， 就相当于更新标号为[1, 3]的线段。**这也是处理线段覆盖问题的通用方法。
对于上面引用中提到的例子中“更新[1,4]，就相当于更新标号为[1,3]的线段”，是因为标号为1的节点代表区间[1,2]，标号为2的节点代表区间[2,3],标号为3的节点代表期间[3,4]
接下来具体讨论这道题目的做法：
将矩形按平行x轴方形构建扫描线（只是思想，不用实际构造），
每个矩形2条平行x轴的边分类{上边，下边}2类，如果我们从下往上“扫描”线，那么[下边]就表示了对答案贡献的开始，[下边]就表示了对答案贡献的结束。
* 扫描线扫描的过程（建议配合代码模拟）
**以下图转载自@kk303的博客**
初始状态
扫到最下边的线, 点1→3更新为1
扫到第二根线, 此时S=lcnt!=0∗h两根线之间, 得到绿色的面积, 加到答案中去, 随后更新计数
同上, 将黄色的面积加到答案中去
同上, 将灰色的面积加到答案中去
同上, 将紫色的面积加到答案中去
1/* ***********************************************
2Author :111qqz
3Created Time :2017年09月27日 星期三 16时37分39秒
4File Name :1542.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=205;
35int n;
36
37double X[N]; //存储所有x坐标，用来离散化。
38//扫描线
39struct Seg
40{
41 double l,r,h;
42 //表示扫面线的起点，终点，所在的高度(y坐标）
43 int d;//1或者-1，表示扫描线对面积是正向影响还是负向影响
44 Seg(){}
45 Seg(double l,double r,double h,int d):l(l),r(r),h(h),d(d){}
46 bool operator < (const Seg &rhs)const
47 {
48 return h<rhs.h;
49 }
50 //从下向上处理扫描线。
51}seg[N];
52struct Tree
53{
54 int cnt;
55 double len;
56}tree[N<<2];
57void PushUp(int l,int r,int rt)
58{
59 /*由于线段树的节点表示的其实是长度为1的区间
60 * 因此线段树的区间[l,r]，对应的点的端点是l,r+1
61 */
62 if (tree[rt].cnt) tree[rt].len = X[r+1]-X[l]; //当前区间已经完全被线段覆盖
63 else if (l==r) tree[rt].len=0; //是叶子节点而且没有被覆盖。
64 else tree[rt].len = tree[rt<<1].len + tree[rt<<1|1].len; //没有完全被覆盖，从其子区间获得信息。
65}
66
67void update( int L,int R,int v,int l,int r,int rt)
68{
69 if (L<=l && r<=R)
70 {
71 tree[rt].cnt+=v;
72 PushUp(l,r,rt);
73 return;
74 }
75 int m = (l+r)>>1;
76 if (L<=m) update(L,R,v,lson);
77 if (R>=m+1) update(L,R,v,rson);
78 PushUp(l,r,rt);
79}
80int main()
81{
82 #ifndef ONLINE_JUDGE
83 freopen("./in.txt","r",stdin);
84 #endif
85 int cas = 0;
86 while (~scanf("%d",&n)&&n)
87 {
88 ms(tree,0);
89 for ( int i = 1 ; i <= n ; i++)
90 {
91 double x1,y1,x2,y2;
92 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
93 seg[i] = Seg(x1,x2,y1,1);
94 seg[i+n]= Seg(x1,x2,y2,-1);
95 X[i] = x1;
96 X[i+n] = x2;
97 }
98 n<<=1;
99 sort(X+1,X+n+1);
100 int m = unique(X+1,X+1+n)-X-1;
101
102 sort(seg+1,seg+n+1);
103 double ans = 0;
104 for ( int i = 1 ; i < n ; i++)
105 {
106 int l = lower_bound(X+1,X+1+m,seg[i].l)-X;
107 int r = lower_bound(X+1,X+1+m,seg[i].r)-X;
108 if (l<r)
109 update(l,r-1,seg[i].d,1,m,1);
110 ans += tree[1].len * (seg[i+1].h-seg[i].h);
111 }
112 printf("Test case #%d\nTotal explored area: %.2f\n\n",++cas,ans);
113
114 }
115
116 #ifndef ONLINE_JUDGE
117 fclose(stdin);
118 #endif
119 return 0;
120}