线段树扫描线 - dblank

线段树扫描线

线段树扫描线可以快速的计算矩形的并面积,在nlogn的复杂度下。

线段树扫描线是把纵坐标离散化,然后对于每个按照高度排好序的线段进行扫描,然后算出扫描线的长度,与高度差进行乘积求面积。一个矩形有两条线段,下线段标记为1代表有一个矩形开始,上线段为-1,代表有个线段截止。

hdu 1542:Atlantis

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 10000 + 10, Mod = 1000000000;
typedef long long ll;
int n, mark[N];
double sum[N], x[N];
struct line
{
    double x1, x2, h;
    int vis;
    line(){};
    line(double _x1, double _x2, double _h, int _vis) : x1(_x1), x2(_x2), h(_h), vis(_vis){}
    bool operator <(const line & rhs) const
    {
        return h < rhs.h;
    }
}L[N];
void pushup(int cnt, int l, int r)
{
    if(mark[cnt]) sum[cnt] = x[r+1] - x[l];
    else if(r==l) sum[cnt] = 0;
    else sum[cnt] = sum[cnt<<1] + sum[cnt<<1|1];
}
void update(int left,int right, int c, int l, int r, int cnt)
{
    if(l>=left && r<=right)
    {
        mark[cnt] += c;
        pushup(cnt, l, r);
        return ;
    }
    int mid = (l+r)>>1;
    if(left<=mid) update(left, right, c, l, mid, cnt<<1);
    if(right>mid) update(left, right,c, mid+1, r, cnt<<1|1);
    pushup(cnt, l, r);
}
int main()
{

    int T = 0;
    while(cin>>n && n)
    {
        int m = 0;
        double x1, x2, y1, y2;
        for(int i = 0; i<n; i++)
        {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            x[++m] = x1;
            L[m] = line(x1, x2, y1, 1);
            x[++m] = x2;
            L[m] = line(x1, x2, y2, -1);
        }
        sort(x+1, x+1+m);
        sort(L+1, L+1+m);
        memset(sum, 0, sizeof(sum));
        memset(mark, 0, sizeof(mark));
        double ans = 0;
        for(int i = 1; i<=m; i++)
        {
            int l = lower_bound(x+1, x+1+m, L[i].x1) - x;
            int r = lower_bound(x+1, x+1+m, L[i].x2) - x -1;
            update(l, r, L[i].vis, 1, m, 1);
            ans += sum[1]*(L[i+1].h - L[i].h);
        }
         printf("Test case #%dnTotal explored area: %.2fnn",++T,ans);
    }
    return 0;
}

 

发表新评论