Atlantis HDU - 1542 （扫描线，线段树）

扫描线的模板题，先把信息接收，然后排序，记录下上边和下边，然后用一条虚拟的线从下往上扫。如果我扫到的是下边，那么久用线段树在这个区间内加上1，表示这个区间现在是有的，等我扫描到上边的时候在加上-1，把之前的消掉，然后线段树维护区间内的长度，这里不是直接用下标维护，而是需要另一个数组来维护，每次记录我当前的下标在原本的图中的长度。

在update部分用一个点表示我这个点以后的一个长度为1的区间，然后这样算出来的sum[1]就是我现在线段树里包括的区间大小，然后用现在的区间大小去乘上这一部分的高度，然后每次相加，就可以了

#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<string>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define lowbit(x) (x & (-x))

typedef unsigned long long int ull;

typedef long long int ll;

const double pi = 4.0*atan(1.0);

const int inf = 0x3f3f3f3f;

const int maxn = ;

const int maxm = ;

using namespace std;

int n, m, tol, T;

struct Node {

    double l, r, h;

    int f;

    bool operator <(Node a) const {

        return h < a.h;

    }

};

Node node[maxn];

double a[maxn];

double sum[maxn << ];

int cnt[maxn << ];

void init() {

    memset(sum, , sizeof sum);

    memset(cnt, , sizeof cnt);

}

void pushup(int left, int right, int root) {

    if(cnt[root] != )        sum[root] = a[right + ] - a[left];

    else if(left == right)    sum[root] = ;

    else    sum[root] = sum[root << ] + sum[root <<  | ];

}

void update(int left, int right, int prel, int prer, int val, int root) {

    if(prel <= left && right <= prer) {

        cnt[root] += val;

        pushup(left, right, root);

        return ;

    }

    int mid = (left + right) >> ;

    if(prel <= mid)    update(left, mid, prel, prer, val, root << );

    if(prer > mid)    update(mid+, right, prel, prer, val, root <<  | );

    pushup(left, right, root);

}

int main() {

    int cas = ;

    while(scanf("%d", &n)==  && n) {

        init();

        double x1, y1, x2, y2;

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

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

            node[*i-].l = x1;

            node[*i].l = x1;

            node[*i-].r = x2;

            node[*i].r = x2;

            node[*i-].h = y1;

            node[*i].h = y2;

            node[*i-].f = ;

            node[*i].f = -;

            a[*i-] = x1;

            a[*i] = x2;

        }

        n = *n;

        sort(node+, node++n);

        sort(a+, a++n);

        int nn = unique(a+, a++n) - (a+);

        double ans = ;

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

            int l = lower_bound(a+, a++nn, node[i].l) - a;

            int r = lower_bound(a+, a++nn, node[i].r) - a;

            update(, nn, l, r-, node[i].f, );

            ans += (node[i+].h - node[i].h) * sum[];

        }

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

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

        printf("\n");

    }

    return ;

}

秒客网

Atlantis HDU - 1542 （扫描线，线段树）

相关文章