覆盖的面积 HDU - 1255 （线段树-扫描线）模板提

时间：2023-03-08 20:39:59
给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

覆盖的面积 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

这题是线段树扫描线水题 

扫描线一开始以为特别难
但是用心去看还是比较容易的
试着用自己的方法理解 
掌握思想

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <ctype.h>

 #include <set>

 #include <map>

 #include <queue>

 #include <stack>

 #include <iostream>

 using namespace std;

 #define bug printf("******\n");

 #define rtl  rt<<1

 #define rtr  rt<<1|1

 typedef long long LL;

 const int maxn = 1e4 + ;

 struct LINE {

     double x, y1, y2;

     int flag;

 } line[maxn];

 int cmp(LINE a, LINE b) {

     return a.x < b.x;

 }

 struct node {

     double x, l, r, pre;

     int flag, cover;

 } tree[maxn << ];

 double y[maxn];

 void build(int l, int r, int rt ) {

     tree[rt].l = y[l], tree[rt].r = y[r];

     tree[rt].pre = , tree[rt].cover = , tree[rt].flag = ;

     if (l +  == r) {

         tree[rt].flag = ;

         return ;

     }

     int m = (l + r) >> ;

     build(l, m, rtl);

     build(m, r, rtr);

 }

 double query(int rt, double x, double y1, double y2, int flag) {

     if (tree[rt].l >= y2 || tree[rt].r <= y1) return ;

     if (tree[rt].flag == ) {

         if (tree[rt].cover > ) {

             double pre = tree[rt].pre;

             double ans = (x - pre) * (tree[rt].r - tree[rt].l);

             tree[rt].pre = x;

             tree[rt].cover += flag;

             return ans;

         } else {

             tree[rt].cover += flag;

             tree[rt].pre = x;

             return ;

         }

     }

     return query(rtl, x, y1, y2, flag) + query(rtr, x, y1, y2, flag);

 }

 int main() {

     int t, n;

     scanf("%d", &t);

     while(t--) {

         scanf("%d", &n);

         int cnt = ;

         for (int i =  ; i < n ; i++) {

             double x1, y1, x2, y2;

             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

             y[cnt] = y1;

             line[cnt].x = x1;

             line[cnt].y1 = y1;

             line[cnt].y2 = y2;

             line[cnt++].flag = ;

             y[cnt] = y2;

             line[cnt].x = x2;

             line[cnt].y1 = y1;

             line[cnt].y2 = y2;

             line[cnt++].flag = -;

         }

         sort(y, y + cnt );

         sort(line, line + cnt, cmp);

         build(, cnt-, );

         double ans = ;

         for (int i =  ; i < cnt ; i++)

             ans += query(, line[i].x, line[i].y1, line[i].y2, line[i].flag);

         printf("%.2f\n", ans);

     }

     return ;

 }

相关文章