学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1255

题义为给定N个矩形，求其重叠的图形面积，该题采用线段树离散化y轴坐标，并且采用分割思想，只依据x坐标来进行分割。

我们将N个矩形化为N*2条线段来处理，该结构体中的成员变量为 x, yl, yh, 分别是x轴坐标，相对高低的y轴坐标，即线段的两个端点值。

1.将所有的线段排一次序，并将y轴所有坐标轴点排序并进行离散化；

2.在从左往右扫描每一条线段时，我们应该理解为此时我们将把该线段的右边区域认定为全部被覆盖；

3.查找该x轴坐标下被覆盖的y轴坐标的次数，因为一旦y轴被覆盖，则说明其右边无限长的区域被覆盖，如果得到 [y1,y2] 这段区间被覆盖了，那么该点到下一个相邻的x轴的坐标之间   
   的区域一定是被覆盖的，那么只要这段区间被覆盖2次或以上，这部分的面积就能够求出来了。

代码如下：

#include <cstdlib>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <algorithm>
#define MAXN 2005
using namespace std;

struct Node
{
double x, yl, yh;
int lr;
bool operator < (Node t) const
    {
return x < t.x;
    }
}e[MAXN];

struct 
{
int l, r, cover;
}seg[3*MAXN];

double yy[MAXN];

void creat(int f, int l, int r)
{
int mid = (l+r)>>1;
    seg[f].l = l, seg[f].r = r;
    seg[f].cover = 0;
if (r - l > 1)
    {
        creat(f<<1, l, mid);
        creat(f<<1|1, mid, r);
    }
}

void modify(int f, int l, int r, int val)
{
int mid = (seg[f].l + seg[f].r)>>1;
if (seg[f].l == l && seg[f].r == r)
    {
        seg[f].cover += val;
    }
else if (seg[f].r - seg[f].l > 1)
    {
if (l >= mid)
            modify(f<<1|1, l, r, val);
else if (r <= mid)
            modify(f<<1, l, r, val);
else
        {
            modify(f<<1, l, mid, val);
            modify(f<<1|1, mid, r, val);
        }
    }
}

void query(int f, double &ans)
{
if (seg[f].cover > 1)
    {
        ans += yy[seg[f].r]-yy[seg[f].l];
//   printf("ans = %lf\n", ans);
    }
else if (seg[f].r - seg[f].l > 1)
    {
//    if (seg[f].cover != 0)
//    {
            seg[f<<1].cover += seg[f].cover;
            seg[f<<1|1].cover += seg[f].cover;
//    seg[f].cover = 0;
//    }
// lazy思想处理的话，该题时间上开销要大很多（往下传递过多），所以采用回溯相对较好
        query(f<<1, ans);
        query(f<<1|1, ans);
        seg[f<<1].cover -= seg[f].cover;
        seg[f<<1|1].cover -= seg[f].cover;
    }
}

int main()
{
int T, N;
double x1, x2, y1, y2, ans, res;
    scanf("%d", &T);
while (T--)
    {
        res = 0;
        map<double,int>mp;
        scanf("%d", &N);
for (int i = 1, j = 1; i <= N; ++i, j+=2)
        {
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
            e[j].x = x1, e[j].yl = y1, e[j].yh = y2;
            e[j].lr = 1;
            e[j+1].x = x2, e[j+1].yl = y1, e[j+1].yh = y2;
            e[j+1].lr = -1;
            yy[j] = y1, yy[j+1] = y2;

        } 
        sort(e+1, e+1+2*N);
        sort(yy+1, yy+1+2*N);
int cnt = unique(yy+1, yy+1+2*N) - (yy+1);
        creat(1, 1, cnt);
for (int i = 1; i <= cnt; ++i)
            mp[yy[i]] = i;
for (int i = 1; i < 2*N; ++i)
        {
            ans = 0;
            modify(1, mp[e[i].yl], mp[e[i].yh], e[i].lr);
            query(1, ans);
            res += ans * (e[i+1].x - e[i].x);
        }
        printf("%.2lf\n", res);
    }
return 0;
}