HDU 1255 覆盖的面积 (线段树 + 离散化 + 扫描线)

Post author:xfxia
Post published:2023年7月22日
Post category:其他

覆盖的面积

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 4304 Accepted Submission(s): 2139

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
      
      
      
      
       
       

      
      
      
      
       
       本博客有扫描线方面的详尽解答，包括这道题目以及一般的扫描线，如果读者需要请到博客中
       
       http://blog.csdn.net/qq_18661257/article/details/47658191
      
      
      
      
       
       #include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r
const int MAXN = 2000 + 5;
int  Col[MAXN << 2], n, cnt, res, T;
double X[MAXN << 2], Sum[MAXN << 2],Sum2[MAXN << 2];
struct seg {
    double l,r,h;
    int s;
    seg() {}
    seg(double l,double r,double h,int s):l(l),r(r),h(h),s(s) {}
    bool operator < (const seg & object) const {
        return h < object.h;
    }
} S[MAXN];


void pushup(int rt,int l,int r) {
    if(Col[rt]) Sum[rt] = X[r + 1] - X[l];
    else if(l == r) Sum[rt] = 0;
    else Sum[rt] = Sum[rt << 1] + Sum[rt << 1|1];

    if(Col[rt] >= 2) Sum2[rt] = X[r + 1] - X[l];
    else if(l == r) Sum2[rt] = 0;
    else if(Col[rt] == 1) Sum2[rt] = Sum[rt << 1] + Sum[rt << 1|1];
    else if(Col[rt] == 0) Sum2[rt] = Sum2[rt << 1] + Sum2[rt << 1|1];
}

void update(int L, int R, int c,int rt,int l, int r) {
    if(L <= l && r <= R) {
        Col[rt] += c;
        pushup(rt,l,r);
        return ;
    }
    int mid = (l + r) >> 1;
    if(L <= mid) update(L, R, c, lson);
    if(R > mid) update(L, R, c, rson);
    pushup(rt,l,r);
}

int binary_find(double x) {
    int lb = -1,ub = res - 1;
    while(ub - lb > 1) {
        int mid = (lb + ub) >> 1;
        if(X[mid] >= x) ub = mid;
        else lb = mid;
    }
    return ub;
}

int main() {
    scanf("%d", &T);
    while(T --) {
        scanf("%d", &n);
        cnt = res = 0;
        for(int i = 0 ; i < n; i ++) {
            double a,b,c,d;
            scanf("%lf%lf%lf%lf",&a, &b, &c,&d);
            S[cnt] = seg(a, c, b, 1);
            X[cnt ++] = a;
            S[cnt] = seg(a, c, d, -1);
            X[cnt ++] = c;
        }
        sort(X, X + cnt);
        sort(S, S + cnt);
        res ++;
        for(int i = 1; i < cnt; i ++) {
            if(X[i] != X[i - 1]) X[res ++] = X[i];
        }

        memset(Sum, 0, sizeof(Sum));
        memset(Col, 0, sizeof(Col));
        memset(Sum2,0,sizeof(Sum2));
        double ans = 0;
        for(int i = 0; i < cnt - 1; i ++) {
            int l = binary_find(S[i].l);
            int r = binary_find(S[i].r) - 1;//利用[ , ),这个区间性质，左闭右开
            update(l, r, S[i].s, 1, 0, res - 1);
            ans += Sum2[1] * (S[i + 1].h - S[i].h);
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}

原文链接：https://blog.csdn.net/qq_18661257/article/details/47658101

覆盖的面积

你可能也喜欢