POJ 1151 / HDU 1542 Atlantis 线段树求矩形面积并

题意：给出矩形两对角点坐标，求矩形面积并。

解法：线段树+离散化。

每加入一个矩形，将两个y值加入yy数组以待离散化，将左边界cover值置为1，右边界置为2，离散后建立的线段树其实是以y值建的树，线段树维护两个值:cover和len,cover表示该线段区间目前被覆盖的线段数目，len表示当前已覆盖的线段长度（化为离散前的真值），每次加入一条线段，将其y_low,y_high之间的区间染上line[i].cover，再以tree[1].len乘以接下来的线段的x坐标减去当前x坐标，即计算了一部分面积。

如图情况，将会计算三次面积：

代码：

#include <iostream>

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#define eps 1e-8

using namespace std;

#define N 307

struct node

{

    int cov;

    double len;

}tree[*N];

struct Line

{

    double y1,y2,x;

    int cov;

}line[*N];

double yy[*N];

int cmp(Line ka,Line kb)

{

    return ka.x < kb.x;

}

int bsearch(int l,int r,double x)

{

    while(l <= r)

    {

        int mid = (l+r)/;

        if(fabs(yy[mid]-x) < eps)

            return mid;

        if(x > yy[mid])

            l = mid+;

        else

            r = mid-;

    }

    return l;

}

void build(int l,int r,int rt)

{

    tree[rt].cov = ;

    tree[rt].len = ;

    if(l == r-) return;

    int mid = (l+r)/;

    build(l,mid,*rt);

    build(mid,r,*rt+);

}

void pushup(int l,int r,int rt)

{

    if(tree[rt].cov)

        tree[rt].len = yy[r]-yy[l];

    else if(l+ == r)

        tree[rt].len = ;

    else

        tree[rt].len = tree[*rt].len + tree[*rt+].len;

}

void update(int l,int r,int aa,int bb,int cover,int rt)

{

    if(aa <= l && bb >= r)

    {

        tree[rt].cov += cover;

        pushup(l,r,rt);

        return;

    }

    if(l+ == r) return;

    int mid = (l+r)/;

    if(aa <= mid)

        update(l,mid,aa,bb,cover,*rt);

    if(bb > mid)

        update(mid,r,aa,bb,cover,*rt+);

    pushup(l,r,rt);

}

int main()

{

    int n,m,cs = ,i,j;

    double x1,y1,x2,y2;

    while(scanf("%d",&n)!=EOF && n)

    {

        m = ;

        for(i=;i<n;i++)

        {

            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

            line[m].x = x1,line[m].y1 = y1,line[m].y2 = y2,line[m].cov = ,yy[m++] = y1;

            line[m].x = x2,line[m].y1 = y1,line[m].y2 = y2,line[m].cov = -,yy[m++] = y2;

        }

        m--;

        sort(yy+,yy+m+);

        int cnt = ;

        for(i=;i<=m;i++)

        {

            if(yy[i] != yy[i-])

                yy[cnt++] = yy[i];

        }

        cnt--;

        build(,cnt,);

        sort(line+,line+m+,cmp);

        double ans = 0.0;

        printf("Test case #%d\n",cs++);

        for(i=;i<m;i++)

        {

            int L = bsearch(,cnt,line[i].y1);

            int R = bsearch(,cnt,line[i].y2);

            update(,cnt,L,R,line[i].cov,);

            ans += tree[].len*(line[i+].x-line[i].x);

        }

        printf("Total explored area: %0.2lf\n\n",ans);

    }

    return ;

}

巴特西

POJ 1151 / HDU 1542 Atlantis 线段树求矩形面积并

最新文章

热门文章