hdu 1255 覆盖的面积 (扫描线+线段树 求矩形面积交)
题意：
求n（1000）个矩形的面积交，也就是至少有2个矩形覆盖的区域的面积。
思路：
面积并问题中，线段树len维护的是至少覆盖一次的区域的长度
在面积交的问题中，我们需要多维护一个"至少覆盖两次的区域的长度"的域（设为double two;）
同时也要维护至少覆盖一次的区域的长度（设为double one;），是因为至少覆盖两次的区域的长度可以由至少覆盖一次的区域长度得到（好像是废话）
PushUp的时候要格外注意当前节点被完整覆盖一次的情况。
此时tree[rt].two 可以由两个子区间的one的情况想加得到
（因为rt节点被完整覆盖了至少一次，那么如果rt儿子区间中被覆盖了至少一次，对于rt区间中被rt«1和rt«1|1覆盖至少一次的区间在对于rt区间就已经覆盖了至少2次）
以及要注意题意说得不够清楚。最后保留2位小数是四舍五入。
读入的实际上是左下角和右上角的点。。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年09月27日 星期三 19时10分37秒
4File Name :1255.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=2E3+7;
35int n;
36struct Seg
37{
38 double l,r,h;
39 int d;
40 Seg(){}
41 Seg(double l,double r,double h,int d):l(l),r(r),h(h),d(d){}
42 bool operator < (const Seg & rhs)const
43 {
44 return h<rhs.h;
45 }
46}a[N];
47struct Tree
48{
49 double one,two; //分别是被覆盖一次以上的长度和被覆盖两次以上的长度。
50 int cnt;
51}tree[N<<2];
52double X[N];
53void PushUp( int l,int r,int rt)
54{
55 //整段区间被完全覆盖2次，长度可以直接得到。
56 if (tree[rt].cnt>=2) tree[rt].one = tree[rt].two = X[r+1]-X[l];
57 else if (tree[rt].cnt==1)
58 {
59 tree[rt].one = X[r+1]-X[l];
60 if (l==r) tree[rt].two = 0;
61 else tree[rt].two = tree[rt<<1].one + tree[rt<<1|1].one;
62 //父节点本身覆盖了一次，这样只需要左右子节点再至少覆盖一次即可。
63 //此处更新是本题唯一的难点。
64 }
65 else
66 {
67 if (l==r) tree[rt].one = tree[rt].two = 0;
68 else
69 {
70 tree[rt].one = tree[rt<<1].one + tree[rt<<1|1].one;
71 tree[rt].two = tree[rt<<1].two + tree[rt<<1|1].two;
72 }
73 }
74}
75void update(int L,int R,int val,int l,int r,int rt)
76{
77 if (L<=l && r<=R)
78 {
79 tree[rt].cnt+=val;
80 PushUp(l,r,rt);
81 return ;
82 }
83 int m = (l+r)>>1;
84 if (L<=m) update(L,R,val,lson);
85 if (R>=m+1) update(L,R,val,rson);
86 PushUp(l,r,rt);
87}
88
89int main()
90{
91 #ifndef ONLINE_JUDGE
92 freopen("./in.txt","r",stdin);
93 #endif
94 int T;
95 scanf("%d",&T);
96 while (T--)
97 {
98 scanf("%d",&n);
99 for ( int i = 1 ; i <= n ; i++)
100 {
101 double x1,y1,x2,y2;
102 //给的坐标实际是左下角和右上角，而不是“左上角和右下角”，题目说错了。
103 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
104 X[i] = x1;
105 X[i+n]=x2;
106 a[i]=Seg(x1,x2,y1,1);
107 a[i+n]=Seg(x1,x2,y2,-1);
108 }
109 n<<=1;
110 sort(X+1,X+n+1);
111 sort(a+1,a+n+1);
112 int m = unique(X+1,X+1+n)-X-1;
113 ms(tree,0);
114 double ans=0;
115 for ( int i = 1 ; i < n ; i++)
116 {
117 int l = lower_bound(X+1,X+m+1,a[i].l)-X;
118 int r = lower_bound(X+1,X+m+1,a[i].r)-X;
119 // cout<<"l:"<<l<<" r:"<<r<<endl;
120 update(l,r-1,a[i].d,1,m,1);
121 ans+=tree[1].two * (a[i+1].h-a[i].h);
122 // cout<<"len:"<<tree[1].two<<" h:"<<a[i+1].h-a[i].h<<" ans:"<<ans<<endl;
123 }
124 //是四舍五入保留2位小数，题目没说清楚。
125 ans = round(ans*100)*0.01;
126 printf("%.2f\n",ans);
127 }
128 #ifndef ONLINE_JUDGE
129 fclose(stdin);
130 #endif
131 return 0;
132}