P - Atlantis - hdu1542（求面积）

题意：rt 求面积......不计算重复面积(废话。。)hdu1255 的弱化版，应该先做这道题在做那道题的。
************************************************************
#include<stdio.h>

#include<algorithm>

#include<math.h>

using namespace std;

#define Lson r<<1

#define Rson r<<1|1

const int MAXN = 1e5+;

struct segmentTree

{///cover记录本区间是否被覆盖,len记录被覆盖的长度

    int L, R, cover;

    double len;

    int mid(){return (L+R)>>;}

}a[MAXN<<];

double Hash[MAXN]; int nh;///记录离散化后的数据

///记录矩形的y边，dir等1表示左边， -1表示右边

struct Edge{double x, y1, y2; int dir;}e[MAXN];

bool cmp(Edge n1, Edge n2)

{///把边按照x从小往大排序

    return n1.x < n2.x;

}

///求y边的长度

double FindEgeLen(int y1, int y2)

{///y1 < y2

    return Hash[y2] - Hash[y1];

}

void BuildSegTree(int r, int L, int R)

{///建立紧密线段树

    a[r].L = L, a[r].R = R;

    a[r].len = a[r].cover = ;

    if(L == R-)return ;

    BuildSegTree(Lson, L, a[r].mid());

    BuildSegTree(Rson, a[r].mid(), R);

}

void PushUp(int r)

{

    if(a[r].cover)

        a[r].len = FindEgeLen( a[r].L, a[r].R );

    else if(a[r].L == a[r].R-)

        a[r].len = ;

    else

        a[r].len = a[Lson].len + a[Rson].len;

}

void UpData(int r, int L, int R, int dir)

{

    if(a[r].L == L && a[r].R == R)

    {

        a[r].cover += dir;

        PushUp(r);

        return ;

    }

    if(R <= a[r].mid())

        UpData(Lson, L, R, dir);

    else if(L >= a[r].mid())

        UpData(Rson, L, R, dir);

    else

    {

        UpData(Lson, L, a[r].mid(), dir);

        UpData(Rson, a[r].mid(), R, dir);

    }

    PushUp(r);

}

int main()

{

    int i, N, t=;

    while(scanf("%d", &N), N)

    {

        double x1, x2, y1, y2, area=; int k = ; nh = ;

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

        {

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

            e[k].x=x1, e[k].y1=y1, e[k].y2=y2, e[k++].dir=;

            e[k].x=x2, e[k].y1=y1, e[k].y2=y2, e[k++].dir=-;

            Hash[nh++] = y1, Hash[nh++] = y2;

        }

        sort(Hash, Hash+nh);

        nh = unique(Hash, Hash+nh)-Hash;

        BuildSegTree(, , nh-);

        sort(e, e+k, cmp);

        for(i=; i<k-; i++)

        {

            int L = lower_bound(Hash, Hash+nh, e[i].y1)-Hash;

            int R = lower_bound(Hash, Hash+nh, e[i].y2)-Hash;

            UpData(, L, R, e[i].dir);

            area += a[].len * (e[i+].x - e[i].x);

        }

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

        printf("Total explored area: %.2f\n\n", area);

    }

    return ;

}
巴特西

P - Atlantis - hdu1542（求面积）

最新文章

热门文章
