POJ 2482 Stars in Your Window（掃描線+線段樹）

【題目連結】 http://poj.org/problem?id=2482

【題目大意】

　　給出一些點的二維坐标和權值，求用一個長H，寬W的矩形能框住的最大權值之和，

　　在矩形邊緣的點不計算在内

【題解】

　　我們計算能掃到這個點的區間範圍，将其拆分為兩條平行于y軸的左閉右開的直線，

　　為友善邊界處理，我們将坐标擴大兩倍，之後我們按照x軸對這些線段進行掃描

　　統計出現的最大值即可。

【代碼】

#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long LL;
const int N=10010;
LL xs[N],ys[N],X[N<<1],Y[N<<1];
int cs[N],tag[N<<3],T[N<<3];
pair<pair<int,int>,pair<int,int> >event[N<<1];
void update(int L,int R,int v,int x,int l,int r){
    if(L<=l&&r<=R){T[x]+=v;tag[x]+=v;return;}
    int mid=(l+r)>>1;
    if(L<=mid)update(L,R,v,x<<1,l,mid);
    if(mid<R)update(L,R,v,x<<1|1,mid+1,r);
    T[x]=max(T[x<<1],T[x<<1|1])+tag[x];
}
int n,W,H;
void solve(){
    for(int i=0;i<n;i++){
        scanf("%lld%lld%d",xs+i,ys+i,cs+i);
        xs[i]<<=1; ys[i]<<=1;
    }
    for(int i=0;i<n;i++){
        X[i<<1]=xs[i]-W; X[i<<1|1]=xs[i]+W;
        Y[i<<1]=ys[i]-H; Y[i<<1|1]=ys[i]-1+H;
    }sort(X,X+n*2);sort(Y,Y+n*2);
    for(int i=0;i<n;i++){
        event[i<<1]=make_pair(make_pair(lower_bound(X,X+n*2,xs[i]-W)-X,cs[i]),make_pair(lower_bound(Y,Y+n*2,ys[i]-H)-Y,lower_bound(Y,Y+n*2,ys[i]+H-1)-Y));
        event[i<<1|1]=make_pair(make_pair(lower_bound(X,X+n*2,xs[i]+W)-X,-cs[i]),make_pair(lower_bound(Y,Y+n*2,ys[i]-H)-Y,lower_bound(Y,Y+n*2,ys[i]+H-1)-Y));
    }sort(event,event+n*2);
		int ans=0;
		for(int i=0;i<n*2;i++){	
			  update(event[i].second.first,event[i].second.second,event[i].first.second,1,0,n*2);
			  ans=max(ans,T[1]);
		}printf("%d\n",ans);
}
int main(){
    while(~scanf("%d%d%d",&n,&W,&H))solve();
    return 0;
}
           

轉載于:https://www.cnblogs.com/forever97/p/poj2482.html