HDU 5091---Beam Cannon（線段樹+掃描線），hdu5091---beam

HDU 5091---Beam Cannon（線段樹+掃描線），hdu5091---beam

題目鏈接

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