首页 > 代码库 > hdu 5091 Beam Cannon（线段树+扫描线+离散化）

hdu 5091 Beam Cannon（线段树+扫描线+离散化）

2024-10-31 18:43:39   211人阅读

Beam Cannon

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 457    Accepted Submission(s): 175


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
2
2
 


题意：在一个平面内有N个人，用一个W*H的矩形去围这些人（边上的也算）， 求最大人数。

思路：以x从小到大排序，y值离散化，投影到y轴上，那么对于每个人的纵坐标，y，y+h就是

每个星星可以影响到的矩形 然后x，x+w+1就是一个进入事件和一个出去事件，其所带的值互

为相反数. node[1].val 保存当前的最大值 当所有的矩形都遍历一遍 取其中的最大值就是ans。


#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=20005;

struct node
{
    int x,y1,y2,val;
    void fun(int xx,int yy1,int yy2,int v)
    {
        x=xx,y1=yy1,y2=yy2;
        val=v;
    }
}b[maxn];
struct tree
{
    int l,r,add,val;
}a[maxn*4];

int n,w,h,cnt,Y[maxn];

bool cmp(node p,node q)
{
    return p.x<q.x;
}

void build(int l,int r,int k)
{
    a[k].l=l,a[k].r=r;
    a[k].add=a[k].val=0;
    if(l==r)  return ;
    int mid=(l+r)/2;
    build(l,mid,2*k);
    build(mid+1,r,2*k+1);
}

void pushdown(int k)
{
    a[2*k].val+=a[k].add;
    a[2*k].add+=a[k].add;
    a[2*k+1].val+=a[k].add;
    a[2*k+1].add+=a[k].add;
    a[k].add=0;
}

void insert(int l,int r,int c,int k)
{
    if(Y[a[k].l]==l && Y[a[k].r]==r)
    {
         a[k].val+=c;
         a[k].add+=c;
    }
    else
    {
         pushdown(k);
         int mid=(a[k].l+a[k].r)/2;
         if(Y[mid]>=r)       insert(l,r,c,2*k);
         else if(Y[mid]<l)   insert(l,r,c,2*k+1);
         else
         {
              insert(l,Y[mid],c,2*k);
              insert(Y[mid+1],r,c,2*k+1);
         }
         a[k].val=max(a[2*k].val,a[2*k+1].val);
    }
}

void input()
{
    cnt=0;
    int x,y;
    scanf("%d %d",&w,&h);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&x,&y);
        y+=20000;
        Y[cnt]=y;
        b[cnt++].fun(x,y,y+h,1);
        Y[cnt]=y+h;
        b[cnt++].fun(x+w+1,y,y+h,-1);
    }
    sort(Y,Y+cnt);
    sort(b,b+cnt,cmp);
    cnt=unique(Y,Y+cnt)-Y;
}

void solve()
{
    build(0,cnt-1,1);
    int ans=0;
    for(int i=0;i<2*n;i++)
    {
        insert(b[i].y1,b[i].y2,b[i].val,1);
        ans=max(ans,a[1].val);
    }
    printf("%d\n",ans);
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n<0)  break;
        input();
        solve();
    }
    return 0;
}



hdu 5091 Beam Cannon（线段树+扫描线+离散化）


联系
我们