hdu1255--覆寫的面積(線段樹+離散化+掃描線)

E - 覆寫的面積 Time Limit:5000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit   Status

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 
           

剛剛接觸掃描線，一開始隻是求了n個矩形的并的體積，這次求的是覆寫兩次以上的面積。

首先給出了n個矩形的坐标，對于y坐标離散化，從左向右掃描，在求并的面積時，用标記sum1存儲了出現過的線段的長度，使用(p[i].x-p[i-1].x)*cl[1].sum1求解了每一部分的面積，而在求覆寫面積的時候，還要定義一個變量sum2，儲存下在控制區内出現兩次的總和。

在sum1的push_up中，如果lazy标記不是0，那麼該段全部出現，那麼cl[rt].sum1 = cl[rt].r - cl[rt].l ;否則該節點的值就是左右兩個子樹的和。

在sum2的push_up中，如果lazy表标記的結果是2，那麼該段全部出現，sum2的值就是該段的長度，如果lazy的标記是1表示該段在該節點全部出現，那麼出現過兩次的長度就是在該節點的左右子節點中出現的長度，即 cl[rt].sum2  = cl[rt<<1].sum1 + cl[rt<<1|1].sum1 ;，如果該節點的lazy是0，那麼該段的sum2也就等于左右子節點的sum2之和。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 3000
struct node1{
    double x, y1 , y2 ;
    int flag ;
} p[maxn];
struct node{
    double l , r ;
    double sum1 , sum2 ;
} cl[maxn<<3];
double s[maxn<<1] ;
int lazy[maxn<<3] ;
bool cmp(node1 a,node1 b)
{
    return a.x <b.x ;
}
void push_up(int rt)
{
    if( lazy[rt] )
        cl[rt].sum1 = cl[rt].r - cl[rt].l ;
    else
        cl[rt].sum1 = cl[rt<<1].sum1 + cl[rt<<1|1].sum1 ;
    if( lazy[rt] > 1 )
        cl[rt].sum2 = cl[rt].r - cl[rt].l ;
    else if(lazy[rt] == 1)
        cl[rt].sum2 = cl[rt<<1].sum1 + cl[rt<<1|1].sum1 ;
    else
        cl[rt].sum2 = cl[rt<<1].sum2 + cl[rt<<1|1].sum2 ;
}
void creat(int rt,int l,int r)
{
    cl[rt].l = s[l] ;
    cl[rt].r = s[r] ;
    if( r - l >1 )
    {
        creat(rt<<1,l,(l+r)/2);
        creat(rt<<1|1,(l+r)/2,r);
        push_up(rt);
    }
    else
    {
        cl[rt].sum1 = cl[rt].sum2 = 0 ;
        cl[rt<<1].sum1 = cl[rt<<1].sum2 = 0 ;
        cl[rt<<1|1].sum1 = cl[rt<<1|1].sum2 = 0 ;
    }
}
void update(int rt,double l,double r,int flag)
{
    if( cl[rt].l== l && cl[rt].r == r )
    {
        lazy[rt] += flag ;
        push_up(rt);
    }
    else
    {
        if( cl[rt<<1].r > l )
        {
            double x = min(r,cl[rt<<1].r);
            update(rt<<1,l,x,flag);
        }
        if( cl[rt<<1|1].l < r )
        {
            double x = max(l,cl[rt<<1|1].l);
            update(rt<<1|1,x,r,flag);
        }
        push_up(rt);
    }
}
int main()
{
    int t , n , m , i , j ;
    double x1, y1 , x2 , y2 , ans ;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(i = 0 ; i < n ; i++)
        {
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
            p[i].x = x1 ;
            p[i].y1 = y1 ;
            p[i].y2 = y2 ;
            p[i].flag = 1 ;
            p[i+n].x = x2 ;
            p[i+n].y1 = y1 ;
            p[i+n].y2 = y2 ;
            p[i+n].flag = -1 ;
            s[i+1] = y1 ;
            s[i+n+1] = y2 ;
        }
        memset(lazy,0,sizeof(lazy));
        sort(s+1,s+2*n+1);
        sort(p,p+2*n,cmp);
        m = unique(s+1,s+(2*n+1))-(s+1);
        creat(1,1,m);
        update(1,p[0].y1,p[0].y2,p[0].flag);
        ans = 0 ;
        for(i = 1 ; i < 2*n ; i++)
        {
            ans += (p[i].x - p[i-1].x)*cl[1].sum2 ;
            update(1,p[i].y1,p[i].y2,p[i].flag);
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}