HDU 5091 Beam Cannon （扫描线思想）

题意：移动一个矩形，使矩形内包含的点尽量多。

思路：把一个点拆成两个事件，一个进（权值为1）一个出（权值为-1），将所有点按照x排序，然后扫描，对于每个x，用一个滑窗计算一下最大值，再移动扫描线。树状数组可以实现。

上面方法其实不是最优的，目前所知最优的办法是把一个矩形压缩成一个点，而一个点延伸为一条线，遇到点的时候更新y+h的一个区间。（线段树懒操作），然后询问线段树上点（矩形）的最值。必须用线段树，时间复杂度会低一些。

类似思路的题目Seoul2007 LA3905，Meteor流星

只写了树状数组版，鉴于扫描线需要进一步学习，待更。

当时做的时候就知道是线段树，可惜我并不会写扫描线，以前尝试写过，挂了，基础有待加强。

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxh = +;

const int maxn = +;

int C[maxh];

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

void add(int x,int v)

{

    while(x <= ){

        C[x] += v; x += lowbit(x);

    }

}

int sum(int x){

    int res = ;

    while(x>){

        res += C[x]; x -= lowbit(x);

    }

    return res;

}

struct Point

{

    int x,y;

    bool operator < (const Point & rhs) const {

        return x < rhs.x;

    }

}poi[maxn];

int main()

{

    //freopen("in.txt","r",stdin);

    int N;

    while(~scanf("%d",&N)&& N>){

        int W,H;

        scanf("%d%d",&W,&H);

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

            scanf("%d%d",&poi[i].x,&poi[i].y);

            poi[i].y += ;

        }

        sort(poi,poi+N);

        int L , R; L = R = ;

        int ans = ;

        while(R<N){

            while(poi[R].x - poi[L].x <= W && R<N){

                add(poi[R++].y,);

            }

            for(int i = ,sz =  - H ; i <= sz ; i++){

                ans = max(ans,sum(i+H)-sum(i-));

            }

            if(R<N)

            while(poi[R].x - poi[L].x > W){

                add(poi[L++].y,-);

            }

        }

        printf("%d\n",ans);

        while(L<N){

            add(poi[L++].y,-);

        }

    }

    return ;

}

巴特西

HDU 5091 Beam Cannon （扫描线思想）

最新文章

热门文章