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位小数是四舍五入。
读入的实际上是左下角和右上角的点。。。。
/* ***********************************************
Author :111qqz
Created Time :2017年09月27日 星期三 19时10分37秒
File Name :1255.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E3+7;
7int n;
8struct Seg
9{
10 double l,r,h;
11 int d;
12 Seg(){}
13 Seg(double l,double r,double h,int d):l(l),r(r),h(h),d(d){}
14 bool operator < (const Seg & rhs)const
15 {
16 return h<rhs.h;
17 }
18}a[N];
19struct Tree
20{
21 double one,two; //分别是被覆盖一次以上的长度和被覆盖两次以上的长度。
22 int cnt;
23}tree[N<<2];
24double X[N];
25void PushUp( int l,int r,int rt)
26{
27 //整段区间被完全覆盖2次，长度可以直接得到。
28 if (tree[rt].cnt>=2) tree[rt].one = tree[rt].two = X[r+1]-X[l];
29 else if (tree[rt].cnt==1)
30 {
31 tree[rt].one = X[r+1]-X[l];
32 if (l==r) tree[rt].two = 0;
33 else tree[rt].two = tree[rt<<1].one + tree[rt<<1|1].one;
34 //父节点本身覆盖了一次，这样只需要左右子节点再至少覆盖一次即可。
35 //此处更新是本题唯一的难点。
36 }
37 else
38 {
39 if (l==r) tree[rt].one = tree[rt].two = 0;
40 else
41 {
42 tree[rt].one = tree[rt<<1].one + tree[rt<<1|1].one;
43 tree[rt].two = tree[rt<<1].two + tree[rt<<1|1].two;
44 }
45 }
46}
47void update(int L,int R,int val,int l,int r,int rt)
48{
49 if (L<=l && r<=R)
50 {
51 tree[rt].cnt+=val;
52 PushUp(l,r,rt);
53 return ;
54 }
55 int m = (l+r)>>1;
56 if (L<=m) update(L,R,val,lson);
57 if (R>=m+1) update(L,R,val,rson);
58 PushUp(l,r,rt);
59}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5 #endif
6 int T;
7 scanf("%d",&T);
8 while (T--)
9 {
10 scanf("%d",&n);
11 for ( int i = 1 ; i <= n ; i++)
12 {
13 double x1,y1,x2,y2;
14 //给的坐标实际是左下角和右上角，而不是“左上角和右下角”，题目说错了。
15 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
16 X[i] = x1;
17 X[i+n]=x2;
18 a[i]=Seg(x1,x2,y1,1);
19 a[i+n]=Seg(x1,x2,y2,-1);
20 }
21 n<<=1;
22 sort(X+1,X+n+1);
23 sort(a+1,a+n+1);
24 int m = unique(X+1,X+1+n)-X-1;
25 ms(tree,0);
26 double ans=0;
27 for ( int i = 1 ; i < n ; i++)
28 {
29 int l = lower_bound(X+1,X+m+1,a[i].l)-X;
30 int r = lower_bound(X+1,X+m+1,a[i].r)-X;
31 // cout<<"l:"<<l<<" r:"<<r<<endl;
32 update(l,r-1,a[i].d,1,m,1);
33 ans+=tree[1].two * (a[i+1].h-a[i].h);
34 // cout<<"len:"<<tree[1].two<<" h:"<<a[i+1].h-a[i].h<<" ans:"<<ans<<endl;
35 }
36 //是四舍五入保留2位小数，题目没说清楚。
37 ans = round(ans*100)*0.01;
38 printf("%.2f\n",ans);
39 }
40 #ifndef ONLINE_JUDGE
41 fclose(stdin);
42 #endif
43 return 0;
44}