首页 > > 程序设计 > C/C++ >

HDU 5091---Beam Cannon（线段树+扫描线）

2018-06-17 23:40:23来源：未知阅读 ()

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=5091

Problem Description

Recently, the γ galaxies broke out Star Wars. Each planet is warring for resources. In the Star Wars, Planet X is under attack by other planets. Now, a large wave of enemy spaceships is approaching. There is a very large Beam Cannon on the Planet X, and it is very powerful, which can destroy all the spaceships in its attack range in a second. However, it takes a long time to fill the energy of the Beam Cannon after each shot. So, you should make sure each shot can destroy the enemy spaceships as many as possible.

To simplify the problem, the Beam Cannon can shot at any area in the space, and the attack area is rectangular. The rectangle parallels to the coordinate axes and cannot rotate. It can only move horizontally or vertically. The enemy spaceship in the space can be considered as a point projected to the attack plane. If the point is in the rectangular attack area of the Beam Cannon(including border), the spaceship will be destroyed.

Input

Input contains multiple test cases. Each test case contains three integers N(1<=N<=10000, the number of enemy spaceships), W(1<=W<=40000, the width of the Beam Cannon’s attack area), H(1<=H<=40000, the height of the Beam Cannon’s attack area) in the first line, and then N lines follow. Each line contains two integers x,y (-20000<=x,y<=20000, the coordinates of an enemy spaceship).

A test case starting with a negative integer terminates the input and this test case should not to be processed.

Output

Output the maximum number of enemy spaceships the Beam Cannon can destroy in a single shot for each case.

Sample Input

2 3 4

0 1

1 0

3 1 1

-1 0

0 1

1 0

-1

Sample Output

Source

2014上海全国邀请赛——题目重现（感谢上海大学提供题目）

Recommend

hujie | We have carefully selected several similar problems for you: 5932 5931 5930 5929 5928

题意：在平面上有n个点，现在有一个平行于坐标轴的矩形，宽为w 高为h，可以上下左右移动，但不能旋转，求这个矩形最多能够围住多少点？

思路：将输入的n个点按照横坐标从小到大排序，为了计算方便，在输入的时候可以对每个点记录一个标记点（打标记），如果输入的点是 node[i].x=x node[i].y=y node[i].v=1 那么加一个标记点node[i+1].x=x+w node[i+1].y=y node[i+1].v= -1 这样对排序后的2*n个点进行计算时，只会有长为w范围的点会被计算，走出w长度范围的点会在计算node[i+1].v=-1 时清理掉。那么现在考虑的点都在长为w的范围内，现在只需要考虑高了，可以用线段树计算对当前点node[i] 把node[i].y~node[i].y+h的区间长度都加上node[i].v 那么线段树求得的最大值就是当前区间点的值了，为什么是这样呢？因为考虑的点都在长为w范围里，所以只需要考虑y值，所以可以转换为这些点在一条直线上，求长为h的线段能覆盖最多的点数，考虑线段的上端点的位置，那么一个点对上端点的贡献为y~y+h 范围，端点的值就是这条线段的覆盖值；

代码如下：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=1e4+5;
int n,w,h;
struct Node
{
    int x,y,v;
}node[2*N];
struct TNode
{
    int f;
    int m;
}tr[16*N];

bool cmp(const Node s1,const Node s2)
{
    if(s1.x==s2.x) return s1.v>s2.v;
    return s1.x<s2.x;
}
void build(int l,int r,int i)
{
    tr[i].f=0; tr[i].m=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
}
void pushdown(int i)
{
    tr[i<<1].f+=tr[i].f;
    tr[i<<1|1].f+=tr[i].f;
    tr[i<<1].m+=tr[i].f;
    tr[i<<1|1].m+=tr[i].f;
    tr[i].f=0;
}
void update(int l,int r,int i,int t)
{
    if(l>=node[t].y&&r<=node[t].y+h)
    {
        tr[i].f+=node[t].v;
        tr[i].m+=node[t].v;
        return ;
    }
    if(tr[i].f!=0)  pushdown(i);
    int mid=(l+r)>>1;
    if(node[t].y<=mid)  update(l,mid,i<<1,t);
    if(node[t].y+h>mid) update(mid+1,r,(i<<1|1),t);
    tr[i].m=max(tr[i<<1].m,tr[i<<1|1].m);
}
int main()
{
    while(scanf("%d",&n)&&n>0)
    {
        scanf("%d%d",&w,&h);
        for(int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            node[2*i-1].x=x;
            node[2*i-1].y=y+2*N;
            node[2*i-1].v=1;
            node[2*i].x=x+w;
            node[2*i].y=y+2*N;
            node[2*i].v=-1;
        }
        sort(node+1,node+2*n+1,cmp);
        build(1,4*N,1);
        int sum=0;
        for(int i=1;i<=2*n;i++)
        {
            update(1,4*N,1,i);
            sum=max(sum,tr[1].m);
        }
        printf("%d\n",sum);
    }
    return 0;
}

补充一下：HDU 4007 和这题相似（2016 ICPC大连站热身赛）

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4007

题意：给了n个点，求一个正方形能围住的最大点数，同样正方形平行于坐标轴；

思路：与上面的题一样，但是这题数据范围很大，线段树的数组开不了这么大，那么必须要进行离散化；

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
typedef long long LL;
LL L,R;
map<LL,LL>p;
struct Node
{
    LL x,y;
    LL v;
}node[3005];
struct TNode
{
    LL m;
    LL f;
}tr[20005];
bool cmp1(const Node s1,const Node s2)
{
    if(s1.x==s2.x)  return s1.v>s2.v;
    return s1.x<s2.x;
}
bool cmp2(const Node s1,const Node s2)
{
    return s1.y<s2.y;
}
void build(LL l,LL r,LL i)
{
    tr[i].m=0;
    tr[i].f=0;
    if(l==r)  return ;
    LL mid=(l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
}
void pushdown(LL i)
{
    tr[i<<1].f+=tr[i].f;
    tr[i<<1|1].f+=tr[i].f;
    tr[i<<1].m+=tr[i].f;
    tr[i<<1|1].m+=tr[i].f;
    tr[i].f=0;
}
void update(LL l,LL r,LL i,LL t)
{
    if(l>=L&&r<=R){
        tr[i].f+=t;
        tr[i].m+=t;
        return ;
    }
    pushdown(i);
    LL mid=(l+r)>>1;
    if(L<=mid) update(l,mid,i<<1,t);
    if(R>mid)  update(mid+1,r,i<<1|1,t);
    tr[i].m=max(tr[i<<1].m,tr[i<<1|1].m);
}
int  main()
{
    LL n,r;
    while(scanf("%lld%lld",&n,&r)!=EOF)
    {
        p.clear();
        for(LL i=1;i<=n;i++)
        {
            LL x,y;
            scanf("%lld%lld",&x,&y);
            node[3*i-2].x=x;
            node[3*i-2].y=y;
            node[3*i-2].v=1;
            node[3*i-1].x=x+r;
            node[3*i-1].y=y;
            node[3*i-1].v=-1;
            node[3*i].x=x;
            node[3*i].y=y+r;
            node[3*i].v=0;
        }
        sort(node+1,node+3*n+1,cmp2);
        ///离散化
        LL tot=0,pre=-1;
        for(LL i=1;i<=3*n;i++)
        {
            if(node[i].y!=pre){
                pre=node[i].y;
                p[pre]=++tot;
            }
        }
        sort(node+1,node+3*n+1,cmp1);
        build(1,tot,1);
        LL sum=0;
        for(LL i=1;i<=3*n;i++)
        {
            if(node[i].v==0) continue;
            L=p[node[i].y];
            R=p[node[i].y+r];
            update(1,tot,1,node[i].v);
            sum=max(sum,tr[1].m);
        }
        printf("%lld\n",sum);
    }
    return 0;
}