HDU1255 覆盖的面积 —— 求矩形交面积线段树 + 扫描线 + 离散化

题目链接：https://vjudge.net/problem/HDU-1255

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

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

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <vector>
  7 #include <queue>
  8 #include <stack>
  9 #include <map>
 10 #include <string>
 11 #include <set>
 12 using namespace std;
 13 typedef long long LL;
 14 const double EPS = 1e-8;
 15 const int INF = 2e9;
 16 const LL LNF = 2e18;
 17 const int MAXN = 1e5+10;
 18 
 19 struct line
 20 {
 21     double le, ri, h;
 22     int id;
 23     bool operator<(const line &a)const{
 24         return h<a.h;
 25     }
 26 }Line[MAXN];
 27 
 28 int times[MAXN<<2];
 29 double X[MAXN], one[MAXN], more[MAXN<<2];
 30 //X用于离散化横坐标，times为此区间被覆盖的次数，
 31 //one为此区间被覆盖一次的长度和， more为此区间至少被覆盖两次的长度和
 32 
 33 void push_up(int u, int l, int r)
 34 {
 35     if(times[u]>=2) //该区间被覆盖了两次
 36     {
 37         more[u] = X[r] - X[l];
 38         one[u] = X[r] - X[l];
 39     }
 40     else if(times[u]==1)    //该区间被覆盖了一次
 41     {
 42         more[u] = one[u*2]+one[u*2+1];
 43         one[u] = X[r] - X[l];
 44     }
 45     else //该区间没有被覆盖
 46     {
 47         if(l+1==r) //该区间为单位区间
 48             more[u] = one[u] = 0;
 49         else
 50         {
 51             more[u] = more[u*2]+more[u*2+1];
 52             one[u] = one[u*2]+one[u*2+1];
 53         }
 54     }
 55 }
 56 
 57 //此种线段树的操作对象为连续型，即最小的元素为长度为1的区间[l,r],其中l和r只代表端点(r-l>=1)，用于确定
 58 //区间的位置和长度，l和r本身没有特别的含义。而以往做的什么单点更新之类的，都属于离散型，在l处和r处是有含义的
 59 void add(int u, int l, int r, int x, int y, int val)
 60 {
 61     if(x<=l && r<=y)
 62     {
 63         times[u] += val;
 64         push_up(u, l, r);
 65         return;
 66     }
 67 
 68     int mid = (l+r)>>1;
 69     if(x<=mid-1) add(u*2, l, mid, x, y, val);
 70     if(y>=mid+1) add(u*2+1, mid, r, x, y, val);
 71     push_up(u, l, r);
 72 }
 73 
 74 int main()
 75 {
 76     int n, T;
 77     scanf("%d", &T);
 78     while(T--)
 79     {
 80         scanf("%d", &n);
 81         for(int i = 1; i<=n; i++)
 82         {
 83             double x1, y1, x2, y2;
 84             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
 85             Line[i].le = Line[i+n].le = x1;
 86             Line[i].ri = Line[i+n].ri = x2;
 87             Line[i].h = y1; Line[i+n].h = y2;
 88             Line[i].id = 1; Line[i+n].id = -1;
 89             X[i] = x1; X[i+n] = x2;
 90         }
 91 
 92         sort(Line+1, Line+1+2*n);
 93         sort(X+1, X+1+2*n);
 94         int m = unique(X+1, X+1+2*n) - (X+1);   //去重
 95 
 96         memset(more, 0, sizeof(more));
 97         memset(one, 0, sizeof(one));
 98         memset(times, 0, sizeof(times));
 99 
100         double ans = 0;
101         for(int i = 1; i<=2*n-1; i++)
102         {
103             int l = upper_bound(X+1, X+1+m, Line[i].le) - (X+1);
104             int r = upper_bound(X+1, X+1+m, Line[i].ri) - (X+1);
105             add(1, 1, m, l, r, Line[i].id);
106             ans += more[1]*(Line[i+1].h-Line[i].h);
107         }
108         printf("%.2f
", ans);
109     }
110 }

View Code

HDU1255 覆盖的面积 —— 求矩形交面积 线段树 + 扫描线 + 离散化

HDU1255 覆盖的面积 —— 求矩形交面积线段树 + 扫描线 + 离散化