FAFU-1398 面積 矩形面積并 線段樹+掃描線

題目連結

HDU1255加強版

#include "stdio.h"
#include "algorithm"
using namespace std;
const int maxn = 2110;
int n;
double y[maxn];
struct node
{
    double x,y1,y2;    //x 邊的位置  y邊的區間大小 
    int f;                //f 标記 前邊還是後邊
}Line[maxn];
struct node1
{
    double y1,y2,len,inlen,mlen;    //  inlen線段被覆寫兩次的長度 mlen覆寫三次的長度
    int ld,rd,c;                 // c為被覆寫次數
}tree[maxn<<2];

bool cmp( node a,node b )
{
    return a.x < b.x;
}

void buildtree( int ld,int rd,int rt)  // 建樹
{
    tree[rt].c = 0;      tree[rt].inlen = 0;
    tree[rt].ld = ld;     tree[rt].rd = rd;
    tree[rt].y1 = y[ld]; tree[rt].y2 = y[rd];
    tree[rt].len = 0;    tree[rt].mlen = 0;
    if( ld+1 == rd )
        return;
    int mid = ( ld+rd )>>1;
    buildtree( ld,mid,rt<<1 );
    buildtree( mid,rd,rt<<1|1 );
}
void PushUp( int rt )
{
    if( tree[rt].c > 2 ){
		tree[rt].len = tree[rt].inlen = 0;
        tree[rt].mlen = tree[rt].y2 - tree[rt].y1;
    }
	else if( tree[rt].c == 2 )
	{
		tree[rt].mlen = tree[rt<<1].len + tree[rt<<1|1].len + tree[rt<<1].inlen + tree[rt<<1|1].inlen + tree[rt<<1].mlen + tree[rt<<1|1].mlen;
		tree[rt].inlen = tree[rt].y2 - tree[rt].y1 - tree[rt].mlen;
		tree[rt].len = 0;
	}
    else if( tree[rt].c == 1 ){
        tree[rt].inlen = tree[rt<<1].len + tree[rt<<1|1].len;  
		tree[rt].mlen = tree[rt<<1].inlen + tree[rt<<1|1].inlen + tree[rt<<1].mlen + tree[rt<<1|1].mlen;
		tree[rt].len = tree[rt].y2 - tree[rt].y1 - tree[rt].inlen - tree[rt].mlen;
    }
    else 
    {
        if( tree[rt].rd - tree[rt].ld == 1 )  //葉子結點
			tree[rt].mlen = tree[rt].inlen = tree[rt].len = 0; 
        else{
            tree[rt].len = tree[rt<<1].len + tree[rt<<1|1].len;
            tree[rt].inlen = tree[rt<<1].inlen + tree[rt<<1|1].inlen;
			tree[rt].mlen = tree[rt<<1].mlen + tree[rt<<1|1].mlen;
        }
    }
}

void updata( int rt,node e )
{
     if( e.y2 < tree[rt].y1 || e.y1 > tree[rt].y2 )
         return;
    if( e.y1 == tree[rt].y1 && e.y2 == tree[rt].y2 )   //線上段樹中找到邊e所在的區間 更新f求出長度冷
    {
        tree[rt].c += e.f;
        PushUp(rt);
        return;
    }
    if( e.y2 <= tree[rt<<1].y2 )   //如果e全在tree[t]的左半邊
        updata( rt<<1,e );
    else if( e.y1 >= tree[rt<<1|1].y1 )  //e在tree[t]的右半邊
        updata( rt<<1|1,e );
    else if( e.y2 > tree[rt<<1|1].y1 && e.y1 < tree[rt<<1].y2 )                               //一部分在左半邊 一部分在右半邊
    {
        node temp = e;
        temp.y2 = tree[rt<<1].y2;
        updata( rt<<1,temp );

        temp = e;
        temp.y1 = tree[rt<<1|1].y1;
        updata( rt<<1|1,temp );
    }
    PushUp(rt);
}
int main()
{
    //freopen("data1.txt","r",stdin);
    int cas,pos;
    double x1,y1,x2,y2,ans;
    scanf("%d",&cas);
    while( cas-- )
    {
        scanf("%d",&n);
        pos = 0;
        for( int i = 1; i <= n; i ++ )
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

            pos++;
            Line[pos].x = x1;                 //存前邊 
            Line[pos].y1 = y1;
            Line[pos].y2 = y2;
            Line[pos].f = 1;
            y[pos] = y1;
            
            pos++;
            Line[pos].x = x2;                  //存後邊
            Line[pos].y1 = y1;
            Line[pos].y2 = y2;
            Line[pos].f = -1;
            y[pos] = y2;            
        }
        sort( y+1,y+pos+1);              //對橫邊進行排序
        sort( Line+1,Line+pos+1,cmp );          //對豎邊進行排序
        buildtree( 1,pos,1 );
        ans = 0;
        for( int i = 1; i <= pos; i ++ )   //當某一條線段被覆寫兩次或兩次以上 計算一次面積
        {
            ans += tree[1].inlen * ( Line[i].x - Line[i-1].x );  //tree[1].len 表示f為1的線段樹長度 Line[i].x - Line[i-1].x相鄰2邊的距離
            updata( 1,Line[i] );
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}