覆盖的面积

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2933 Accepted Submission(s): 1447

Problem Description

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

Input

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.
注意:本题的输入数据较多,推荐使用scanf读入数据.

Output

对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.

Sample Input

2

5

1 1 4 2

1 3 3 7

2 1.5 5 4.5

3.5 1.25 7.5 4

6 3 10 7

3

0 0 1 1

1 0 2 1

2 0 3 1

Sample Output

7.63

0.00 

Author

Ignatius.L & weigang Lee

【题解】：

举个例子吧：

10 10 20 20

15 15 25 25

首先取得所有线段以及 y 的数组

y: 10 20 15 25

排序后： y:10 15 20 25

建树:

[15,25]

　　　　[10,15]　[15,25]

　　　　　　　[15,20] [20,25]　　　

叶子节点有：[10,15],[15,20],[20,25]

如图：

line1： x=10 y1=10 y2=20 flag=1

line2： x=15 y1=15 y2=25 flag=1

line3： x=20 y1=10 y2=20 flag=-1

line1： x=25 y1=15 y2=25 flag=-1

对叶子节点：[10,15],[15,20],[20,25]

扫描从 line1 到 line4 ：

line1:找到[y1,y2]覆盖的叶子节点 [10,15],[15,20]，改变其cover值：cover+=line1.flag,此时[10,15]的cover=1，[15,20]的cover=1；

line2:找到[y1,y2]覆盖的叶子节点 [15,20],[20,25]，改变其cover值：cover+=line2.flag,此时[15,20]的cover=2，[20,25]的cover=1；

line3:找到[y1,y2]覆盖的叶子节点 [10,15],[15,20]，发现[15,20]的cover>=2,计算面积，改变其cover值：cover+=line3.flag,因为line3.flag=-1，此时[10,15]的cover=0，[15,20]的cover=1；

line4:找到[y1,y2]覆盖的叶子节点 [15,20],[20,25]，改变其cover值：cover+=line4.flag,因为line4.flag=-1，此时[15,20]的cover=0，[20,25]的cover=0；

结束遍历。

【code】：

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<algorithm>
  4 
  5 using namespace std;
  6 #define N 1005
  7 
  8 // 定义线段，每个矩形看成两条竖线
  9 struct Line
 10 {
 11     double x,y1,y2;
 12     int flag;  // 1表示入边，-1表示出边 ,算覆盖的时候要用
 13 }line[N<<1];
 14 
 15 // 定义线段树的节点，其中x，y1<y2 分别对应线段的坐标
 16 struct Nod
 17 {
 18     int l,r;    // 离散化，Y[l]和Y[r]表示节点所覆盖的Y轴上的范围
 19     double x,y1,y2;
 20     int cover;  // 记录线段覆盖的次数
 21 }node[N<<3];
 22 
 23 double yy[N<<1];    // 保存纵坐标，用于排序
 24 
 25 bool cmp(Line a,Line b)   // 比较函数，用于对线段进行排序
 26 {
 27     return a.x<b.x;
 28 }
 29 
 30 void building(int l,int r,int p)    // 构建线段树
 31 {
 32     node[p].l = l;
 33     node[p].r = r;
 34     node[p].cover = 0;
 35     node[p].y1 = yy[l];
 36     node[p].y2 = yy[r];
 37     if(l+1==r)  return;     //到达叶子
 38     int mid = (l+r)>>1;
 39     building(l,mid,p<<1);
 40     building(mid,r,p<<1|1);  //注意不是mid+1，因为叶子节点要计算长度
 41 }
 42 
 43 // 更新线段树，插入新的线段，每次插入如果完全覆盖则要对cover进行更新
 44 double update(Line le,int p)
 45 {
 46     // 如果当前线段完全没有被覆盖
 47     if(node[p].y2<=le.y1||node[p].y1>=le.y2)    return 0;
 48     if(node[p].l+1==node[p].r)  //叶子
 49     {
 50         if(node[p].cover<2)  // 覆盖次数小于2的时候，更新cover值，以及记录当前x坐标
 51         {
 52             node[p].cover+=le.flag;
 53             node[p].x = le.x;
 54             return 0;
 55         }
 56         else    // 覆盖次数大于等于2的叶子节点则直接计算覆盖区间
 57         {
 58             double res = (le.x-node[p].x)*(node[p].y2-node[p].y1);
 59             node[p].cover+=le.flag;
 60             node[p].x = le.x;
 61             return res;
 62         }
 63     }
 64     return update(le,p<<1)+update(le,p<<1|1);  //面积为叶子节点面积之和
 65 }
 66 
 67 int main()
 68 {
 69     int t;
 70     scanf("%d",&t);
 71     while(t--)
 72     {
 73         int n;
 74         scanf("%d",&n);
 75         int i,cnt=1;    // 记录竖线的数量（注意最后多1）
 76         double x1,y1,y2,x2;
 77         // 输入并保存y坐标和竖线
 78         for(i=1;i<=n;i++)
 79         {
 80             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 81             yy[cnt] = y1;
 82             line[cnt].x = x1;
 83             line[cnt].y1 = y1;
 84             line[cnt].y2 = y2;
 85             line[cnt++].flag = 1;
 86 
 87             yy[cnt] = y2;
 88             line[cnt].x = x2;
 89             line[cnt].y1 = y1;
 90             line[cnt].y2 = y2;
 91             line[cnt++].flag = -1;
 92         }
 93         // 对纵坐标和线段进行排序
 94         sort(yy+1,yy+cnt);
 95         sort(line+1,line+cnt,cmp);
 96         building(1,cnt-1,1);
 97         double ans = 0;
 98         // 扫描线从左到右进行
 99         for(i=1;i<cnt;i++)
100         {
101             ans+=update(line[i],1);
102         }
103         printf("%.2lf
",ans);
104     }
105     return 0;
106 }