POJ2482 Stars in Your Window

Description

（一段令人感動的程式員的愛情故事...）

Here comes the problem: Assume the sky is a flat plane. All the stars lie on it with a location (x, y). for each star, there is a grade ranging from 1 to 100, representing its brightness, where 100 is the brightest and 1 is the weakest. The window is a rectangle whose edges are parallel to the x-axis or y-axis. Your task is to tell where I should put the window in order to maximize the sum of the brightness of the stars within the window. Note, the stars which are right on the edge of the window does not count. The window can be translated but rotation is not allowed. 

Input

There are several test cases in the input. The first line of each case contains 3 integers: n, W, H, indicating the number of stars, the horizontal length and the vertical height of the rectangle-shaped window. Then n lines follow, with 3 integers each: x, y, c, telling the location (x, y) and the brightness of each star. No two stars are on the same point. 

There are at least 1 and at most 10000 stars in the sky. 1<=W，H<=1000000, 0<=x，y<2^31. 

Output

For each test case, output the maximum brightness in a single line.

Sample Input

3 5 4
1 2 3
2 3 2
6 3 1
3 5 4
1 2 3
2 3 2
5 3 1
      

Sample Output

5
6      

題意：給出若幹星星的坐标及其亮度，給定一個矩形W*H，求可以圍住的星星亮度之和的最大值(恰好在邊上的不算）。

分析：将矩形抽象為矩形的中心點，每個星星可以被圍住的範圍可以看做以星星所在坐标為中心點的矩形，将所有星星對應的矩形分别賦予相應的權值c，則該平面内權值之和最大的區域即為所求的矩形中心點所在的位置。記錄每個矩形左右兩邊的橫坐标和上下界，分别賦予正負權值，利用掃描線從左到右掃描，更新線段樹，将縱邊對應的區間加上相應的權值，得到全局最大值即可得到最終結果。

需要注意的是恰好在邊上的星星不算，是以需要考慮邊界問題：兩條縱邊重合時，要先處理-c那條邊；對于橫邊框，記錄每條縱邊上下界時可記為區間[y1,y2-1]。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20010;
typedef long long ll;
ll Y[maxn];
struct node{
	int max,tag;
}tree[maxn<<2];
struct Edge{	
	ll low,high,x;//上下縱坐标、橫坐标 
	int c;//亮度 	
	Edge(){}
	Edge(ll l,ll h,ll x,int c)
	:low(l),high(h),x(x),c(c){}
	
	bool operator<(const Edge other)
	{
		if(x==other.x)//橫坐标重合時 先處理負權值邊 
			return c<other.c;
		return x<other.x;
	} 
}edge[maxn];

void update(int L,int R,int root,int l,int r,int val)
{
	if(L<=l&&R>=r)
	{
		tree[root].max+=val;
		tree[root].tag+=val;
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid) update(L,R,root<<1,l,mid,val);
	if(R>mid) update(L,R,root<<1|1,mid+1,r,val);
	
	tree[root].max=max(tree[root<<1].max,tree[root<<1|1].max)+tree[root].tag;
}

int main()
{
	int N,W,H,num;
	while(cin>>N>>W>>H)
	{	
		num=0;	
		//memset(tree,0,sizeof(tree));
		for(int i=0;i<N;i++)
		{
			ll x,y,c;
			scanf("%lld%lld%d",&x,&y,&c);
			x*=2;y*=2;//乘2以避免除法出現誤差 
			edge[num]=Edge(y-H,y+H-1,x-W,c);//上界減一 
			Y[num++]=y-H;
			edge[num]=Edge(y-H,y+H-1,x+W,-c);//負權值 
			Y[num++]=y+H-1;//上界減一 
			
		}
		//對橫坐标排序，從左到右掃描 
		sort(edge,edge+num);		
		//準備離散化 
		sort(Y,Y+num);
		num=unique(Y,Y+num)-Y; 
		int ans=0;
		for(int i=0;i<N*2;i++)
		{
			int low=lower_bound(Y,Y+num,edge[i].low)-Y;
			int high=lower_bound(Y,Y+num,edge[i].high)-Y;
			update(low,high,1,0,num,edge[i].c);//更新線段樹 
			ans=max(ans,tree[1].max);//求最大權值 
		} 
		cout<<ans<<endl;
	}
	return 0;	
}