Beam Cannon

2 3 4
0 1
1 0
3 1 1
-1 0
0 1
1 0
-1

2
2

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

题意：有n个点，给你w*h的框框，问你最多可以框住几个点，边缘也算。

做法：把每个点x-w/2，y-h/2，  与x+w/2，y+h /2，作一个矩形，可以知道，只有那个框框的中心在这个矩形中就可以覆盖这个点。然后就把所有点的矩形画出来，计算最大重合的层数就行了。实际操作中  可以把每个矩形看作  左下角为 x，y，右上角为x+w，y+h。 也就相当于一起平移。最大重合层数不变。

这题和我之前做得算面积的线段树不同。因为这里关注的不在是面积，所以也就不再关注宽度了。所以这里 线段树里的每个点0-（k-1）代表的不是一段长度的状态了，而是每一个点的状态。

所以本来的 r=Bin(s[i].r,k,x)-1;这一句 由原模版变成了r=Bin(s[i].r,k,x)。

然后就是基本功，把线段树改成算最大值的了。cover记录每个区间最大值。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<set>
#define ll __int64
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const ll maxn=50010;

struct Seg
{
	ll l,r,h;
	ll flag;
	Seg(){}
	Seg(ll a,ll b,ll c,ll d):l(a),r(b),h(c),flag(d){}
	bool operator<(const Seg &hh) const 
	{
		return h<hh.h;
	}
};

struct Seg s[maxn<<3];
ll cover[maxn<<2],add[maxn<<2];
ll x[maxn<<2];
ll ans;
void PushUp(ll rt,ll l,ll r)
{
	cover[rt]=max(cover[rt<<1],cover[rt<<1|1])+add[rt];
}

void Update(ll L,ll R,ll f,ll l,ll r,ll rt)
{
	if(L<=l && r<=R)
	{
		cover[rt]+=f;//这个点的覆盖
		add[rt]+=f; 
		return ;
	}
	ll m=(l+r)>>1;
	if(R<=m) Update(L,R,f,lson);
	else if(L>m) Update(L,R,f,rson);
	else
	{
		Update(L,R,f,lson);
		Update(L,R,f,rson);
	}
	PushUp(rt,l,r);
}

ll Bin(ll k,ll n,ll x[])
{
	ll l,r,m;
	l=0,r=n-1;
	while(l<=r)
	{
		m=(l+r)>>1;
		if(x[m]==k) return m;
		else if(x[m]>k) r=m-1;
		else l=m+1;
	}
	return -1;
}
set<ll> ss;
set<ll>::iterator it;
int main()
{
	ll n;
	ll i;
	ll ww,hh;
	
	ll xx,yy;
	while(scanf("%I64d",&n),n!=-1)
	{
		
		scanf("%I64d%I64d",&ww,&hh);
		ll m=0;
		ss.clear();
		for(i=0;i<n;i++)
		{ 
			scanf("%I64d %I64d",&xx,&yy);

			ss.insert(xx+ww);
			ss.insert(xx);

			s[m++]=Seg(xx,xx+ww,yy,1);
			s[m++]=Seg(xx,xx+ww,yy+hh,-1); 
		}
		sort(s,s+m);
		ll k=0;
		for(it=ss.begin();it!=ss.end();it++)
			x[k++]=*it;

		memset(cover,0,sizeof cover);
		memset(add,0,sizeof add);

		ans=0;
		for(i=0;i<m-1;i++)
		{
			ll l=Bin(s[i].l,k,x);
			ll r=Bin(s[i].r,k,x);
			if(l<=r) Update(l,r,s[i].flag,0,k-1,1);
			ans=max(ans,cover[1]); 
		}
		printf("%I64d\n",ans);
	}
	return 0;

} 

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

原文：http://blog.csdn.net/u013532224/article/details/45508503