HDU 1255 覆寫的面積

覆寫的面積

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

Total Submission(s): 2494    Accepted Submission(s): 1237

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
  
  
    
  
  
       這個題目以前做過，當時剛開始學習線段樹，是以在網上看了一個代碼，效率不高，但是過了，後來發現看那個代碼會忽略線段樹的精髓，今天做HDU4419的時候受到啟發，于是重寫改寫了一下，效率提高很多，我覺得這個算法應該就是排行上前幾名的算法了，453MS，雖然不是第一名的265MS，但這個也隻是是否保留标記的問題。
  
  
       這個算法的核心就在于setlen()函數，這裡我做了三個長度，分别是len[0],len[1],len[2]分别表示沒有覆寫，覆寫一次，以及覆寫2次和兩次以上的線段長度。然後通過轉移方程，就可以友善計算了。而且不用每次都計算到葉子結點。
  
  
       下面上代碼
  
  
    
  
  
    
  
  
          
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;
const int maxn=1001;
struct Line
{
    double x1,x2,y;
    int flag;
}line[2*maxn];
struct node
{
    int l,r,cover;
    double len[3];
    int getmid()
    {
        return (l+r)/2;
    }
}tree[8*maxn];
double X[2*maxn];
int k;
int n;
int cmp(Line a,Line b)
{
    return a.y<b.y;
}
void build(int l,int r,int u)
{
    tree[u].l=l;
    tree[u].r=r;
    tree[u].len[1]=tree[u].len[2]=tree[u].cover=0;
    tree[u].len[0]=X[r]-X[l];
    if (r-l==1)
        return ;
    int mid=tree[u].getmid();
    build(l,mid,2*u);
    build(mid,r,2*u+1);
}
void setlen(int u)
{
    int l=tree[u].l,r=tree[u].r;
    if (r-l==1)
    {
        if (tree[u].cover>1)
        {
            tree[u].len[0]=0;
            tree[u].len[1]=0;
            tree[u].len[2]=X[r]-X[l];
        }
        else if (tree[u].cover==1)
        {
            tree[u].len[2]=tree[u].len[0]=0;
            tree[u].len[1]=X[r]-X[l];
        }
        else
        {
            tree[u].len[1]=tree[u].len[2]=0;
            tree[u].len[0]=X[r]-X[l];
        }
    }
    else
    {
        if (tree[u].cover>1)
        {
            tree[u].len[0]=0;
            tree[u].len[1]=0;
            tree[u].len[2]=X[r]-X[l];
        }
        else if (tree[u].cover==1)
        {
            tree[u].len[0]=0;
            tree[u].len[1]=tree[2*u].len[0]+tree[2*u+1].len[0];
            tree[u].len[2]=tree[2*u].len[1]+tree[2*u+1].len[1]+tree[2*u].len[2]+tree[2*u+1].len[2];
        }
        else
        {
            tree[u].len[0]=tree[2*u].len[0]+tree[2*u+1].len[0];
            tree[u].len[1]=tree[2*u].len[1]+tree[2*u+1].len[1];
            tree[u].len[2]=tree[2*u].len[2]+tree[2*u+1].len[2];
        }
    }
}
void updata(int l,int r,int u,int flag)
{
    if (tree[u].r==r&&tree[u].l==l)
    {
        tree[u].cover+=flag;
        setlen(u);
        return ;
    }
    int mid=tree[u].getmid();
    if (r<=mid)
    {
        updata(l,r,2*u,flag);
    }
    else if (l>=mid)
    {
        updata(l,r,2*u+1,flag);
    }
    else
    {
        updata(l,mid,2*u,flag);
        updata(mid,r,2*u+1,flag);
    }
    setlen(u);
}

int main()
{
    int count,i,j;
    int t;
    double x1,x2,y1,y2;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        count=0;
        for (i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            count++;
            X[count]=x1;
            line[count].x1=x1;
            line[count].x2=x2;
            line[count].y=y1;
            line[count].flag=1;
            count++;
            X[count]=x2;
            line[count].x1=x1;
            line[count].x2=x2;
            line[count].y=y2;
            line[count].flag=-1;
        }
        sort(X+1,X+1+count);
        sort(line+1,line+1+count,cmp);
        k=unique(X+1,X+1+count)-X-1;
        map<double,int> m;
        for (i=1;i<=k;i++)
            m.insert(map<double,int>::value_type(X[i],i));
        double ans=0;
        build(1,k,1);
        int i=1;
        while(i<=count)
        {
            j=i;
            while(j<=count&&line[j].y==line[i].y)
            {
                int l=m[line[j].x1];
                int r=m[line[j].x2];
                updata(l,r,1,line[j].flag);
                j++;
            }
            if (j<=count)
                ans+=tree[1].len[2]*(line[j].y-line[i].y);
            i=j;
        }
        printf("%.2f\n",ans);
    }
    return 0;
}