C++11(clang++ 3.9) 解法, 执行用时: 802ms, 内存消耗: 25596K, 提交时间: 2017-12-18 17:21:02

#include<bits/stdc++.h>
using namespace std;
/*ChiMu Yuan*/
 
const int maxn = 100005;
 
int n, m;
double x[maxn << 1], sumw[maxn << 3];
int add[maxn << 3];
 
struct Width
{
    double l, r, h;
    int stu;
 
    Width(){}
    Width(double a, double b, double c, int d) : l(a), r(b), h(c), stu(d) {}
 
    bool operator < (const Width w) const
    {
        return this->h < w.h;
    }
}width[maxn << 1];
 
void pushup(int id, int l, int r)
{
    if(add[id])
        sumw[id] = x[r - 1] - x[l - 1];
    else if(r - l == 1)
        sumw[id] = 0;
    else
        sumw[id] = sumw[id << 1] + sumw[id << 1 | 1];
    return ;
}
 
void update(int l, int r, int L, int R, int stu, int id)
{
    if(l <= L && R <= r)
    {
        add[id] += stu;
        pushup(id, L, R);
        return ;
    }
    if(R - L <= 1)
        return ;
    int mid = (L + R) >> 1;
    if(r <= mid)
        update(l, r, L, mid, stu, id << 1);
    else if(mid <= l)
        update(l, r, mid, R, stu, id << 1 | 1);
    else
    {
        update(l, r, L, mid, stu, id << 1);
        update(l, r, mid, R, stu, id << 1 | 1);
    }
    pushup(id, L, R);
    return ;
}
 
int main()
{
//    freopen("max.in", "r", stdin);
//    freopen("max.out", "w", stdout);
    double x1, y1, x2, y2;
    double area;
    int cnt, l, r;
    while(~scanf("%d%d", &n, &m))
    {
        memset(sumw, 0, sizeof(sumw));
        memset(add, 0, sizeof(add));
        cnt = area = 0;
        for(int i = 0; i < n; i ++)
        {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            x[cnt] = x1;
            width[cnt ++] = Width(x1, x2, y1, 1);
            x[cnt] = x2;
            width[cnt ++] = Width(x1, x2, y2, -1);
        }
        sort(width, width + cnt);
        sort(x, x + cnt);
        cnt = unique(x, x + cnt) - x;
        for(int i = 0; i < n + n - 1; i ++)
        {
            l = lower_bound(x, x + cnt, width[i].l) - x;
            r = lower_bound(x, x + cnt, width[i].r) - x;
            update(l + 1, r + 1, 1, cnt, width[i].stu, 1);
            area += sumw[1] * (width[i + 1].h - width[i].h);
        }
        memset(sumw, 0, sizeof(sumw));
        memset(add, 0, sizeof(add));
        cnt = 0;
        for(int i = 0; i < m; i ++)
        {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            x[cnt] = x1;
            width[cnt ++] = Width(x1, x2, y1, 1);
            x[cnt] = x2;
            width[cnt ++] = Width(x1, x2, y2, -1);
        }
        sort(width, width + cnt);
        sort(x, x + cnt);
        cnt = unique(x, x + cnt) - x;
        for(int i = 0; i < m + m - 1; i ++)
        {
            l = lower_bound(x, x + cnt, width[i].l) - x;
            r = lower_bound(x, x + cnt, width[i].r) - x;
            update(l + 1, r + 1, 1, cnt, width[i].stu, 1);
            area -= sumw[1] * (width[i + 1].h - width[i].h);
        }
        printf("%.2f\n", area);
    }
    return 0;
}