Get The Treasury HDU - 3642（扫描线求三维面积交。。体积交）

题意：

。。。就是求体积交。。。

解析：

　　把每一层z抽出来，计算面积交， 然后加起来即可。。！

去看一下 二维面积交的代码 再看看这个三维面积交的代码。。 down函数里 你发现了什么规律！！！

参考二维面积交：https://www.cnblogs.com/WTSRUVF/p/9274318.html

代码如下

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

const int maxn = , INF = 0x7fffffff;

typedef long long LL;

int X[maxn];

struct node{

    int l, r, w;

    int lx, rx, sum, lsum, llsum;

}Node[maxn];

struct edge{

    int lxx, rxx, y, z1, z2;

    int f;

}Edge[maxn*];

int cmp(edge a, edge b)

{

    return a.y < b.y;

}

void build(int k, int ll, int rr)

{

    Node[k].l = ll, Node[k].r = rr;

    Node[k].w = Node[k].sum = Node[k].lsum = Node[k].llsum = ;

    Node[k].lx = X[ll];

    Node[k].rx = X[rr];

    if(ll +  == rr) return;

    int m = (ll + rr) / ;

    build(k*, ll, m);

    build(k*+, m, rr);

}

void down(int k)

{

    int len = Node[k].rx - Node[k].lx;

    if(Node[k].w >= )

    {

        Node[k].sum = Node[k].lsum = Node[k].llsum = len;

    }

    else if(Node[k].w == )

    {

        Node[k].lsum = Node[k].llsum = len;

        if(Node[k].l +  == Node[k].r)

            Node[k].sum = ;

        else

            Node[k].sum = Node[k*].lsum + Node[k*+].lsum;

    }

    else if(Node[k].w == )

    {

        Node[k].lsum = len;

        if(Node[k].l +  == Node[k].r)

            Node[k].llsum = Node[k].sum = ;

        else

        {

            Node[k].llsum = Node[k*].lsum + Node[k*+].lsum;

            Node[k].sum = Node[k*].llsum + Node[k*+].llsum;

        }

    }

    else

    {

        if(Node[k].l +  == Node[k].r)

            Node[k].sum = Node[k].lsum = Node[k].llsum = ;

        else

        {

            Node[k].lsum = Node[k*].lsum + Node[k*+].lsum;

            Node[k].llsum = Node[k*].llsum + Node[k*+].llsum;

            Node[k].sum = Node[k*].sum + Node[k*+].sum;

        }

    }

}

void update(int k, edge e)

{

    if(Node[k].lx == e.lxx && Node[k].rx == e.rxx)

    {

        Node[k].w += e.f;

        down(k);

        return;

    }

    if(e.rxx <= Node[k*].rx) update(k*, e);

    else if(e.lxx >= Node[k*+].lx) update(k*+, e);

    else

    {

        edge temp = e;

        temp.rxx = Node[k*].rx;

        update(k*, temp);

        temp = e;

        temp.lxx = Node[k*+].lx;

        update(k*+, temp);

    }

    down(k);

}

int main()

{

    int T, kase = ;

    scanf("%d",&T);

    while(T--)

    {

        int n, cnt = ;

        scanf("%d",&n);

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

        {

            int x1, y1, z1, x2, y2, z2;

            scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);

            Edge[++cnt].lxx = x1, Edge[cnt].rxx = x2, Edge[cnt].y = y1, Edge[cnt].f = , Edge[cnt].z1= z1, Edge[cnt].z2 = z2;

            X[cnt] = x1;

            Edge[++cnt].lxx = x1, Edge[cnt].rxx = x2, Edge[cnt].y = y2, Edge[cnt].f = -, Edge[cnt].z1= z1, Edge[cnt].z2 = z2;

            X[cnt] = x2;

        }

        sort(Edge+, Edge+cnt+, cmp);

        sort(X+, X+cnt+);

        int m = unique(X+, X+cnt+) - (X+);

        LL ret = ;

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

        {

            build(, , m);

            int ans = ;

            edge line[maxn];

            for(int j=; j<=cnt; j++)

            {

                if(Edge[j].z1 <= i && Edge[j].z2 > i)

                    line[++ans] = Edge[j];

            }

            for(int j=; j<ans; j++)

            {

                update(, line[j]);

                ret += (LL)Node[].sum * (line[j+].y - line[j].y);

            }

        }

        printf("Case %d: %lld\n",++kase,ret);

    }

    return ;

}