POJ 2482 Stars in Your Window 题解 《挑战程序设计竞赛》

POJ 2482 Stars in Your Window

数星星：夜空有n个星星，坐标(x,y)亮度c。用长W宽H的窗户去套，问能套住的星星的亮度之和的最大值？

3.6与平面和空间打交道的计算几何 

平面扫描 

引子还讲述了一理工男暗恋女神4年，到毕业都不敢约出来吃个饭的悲催故事。充分体现了广大码农的尿性，这事儿应该速战速决，因为结果事先就确定了，不取决于你有多努力。

言归正传，一开始我第一个想法是，跟《 POJ 1981 Circle and Points 》很像，不过那题是圆，而且允许点在圆上，所以不能用极限情况来操作。

换个思路，每个点能被套住的范围是有限的。将矩形抽象为一个点——矩形的中心点，则每个点能被矩形套住的范围是一个以该点为中心点，大小和原矩形一致的矩形。那么我们就得到了n个矩形，这些矩形会彼此相交，将平面分割为许多区间。为每个矩形分配亮度c作为权值，那么每个区间表示把矩形中心点放在这里，能套住的星星的亮度之和，问题转化为求解范围内的极值（RMQ）。

具体说来，将每个矩形表示为两个垂直于x轴的线段(x1,y1,y2,c)和(x2,y1,y2,-c)，分别表示x坐标、下界、上界、亮度。从左往右扫描，分析线段维护线段树，也即将y1和y2区间的值加上对应的权值（或负权值），用全域最大值更新答案即可。

在实施的时候，当两条线段重合的时候，必须先处理-c那条，这样就不会将竖边框上的星星算上去了。至于横边框，也就是y值的处理，可以让线段树控制半开半闭区间[y1,y2)，也可以将y2故意多减一，这样在到达边框前，亮度就已经失效了。而y1的加c虽然对自己也生效，但是题目保证没有两颗星星重合，所以y1线段也不会造成多算。

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX_N 10000
typedef long long LL;

LL xs[MAX_N];	// 横坐标
LL ys[MAX_N];	// 纵坐标
int cs[MAX_N];	// 亮度
LL X[MAX_N * 2];	// 以每个星星为中心的窗口的左右横坐标
LL Y[MAX_N * 2];	// 以每个星星为中心的窗口的上下纵坐标
pair<pair<int, int>, pair<int, int> > event[MAX_N * 2]; // (x,add),(y1,y2) 一条线段，add为亮度

////////////////////////线段树维护区域最大值/////////////////////////////////
int node_value[MAX_N * 8], node_max[MAX_N * 8];
// 将[from, to]区间的节点对应的值增加v，同时维护节点对应区域的最大值
void add(int from, int to, int v, int i, int l, int r)
{
	if (from <= l && r <= to)
	{
		node_value[i] += v;
		node_max[i] += v;
		return;
	}
	int m = (l + r) >> 1;
	if (from <= m) add(from, to, v, i * 2, l, m);
	if (m < to) add(from, to, v, i * 2 + 1, m + 1, r);
	node_max[i] = max(node_max[i * 2], node_max[i * 2 + 1]) + node_value[i];
}
////////////////////////线段树结束/////////////////////////////////////////

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n, W, H;
	while (~scanf("%d%d%d", &n, &W, &H))
	{
		for (int i = 0; i < n; ++i)
		{
			scanf("%lld%lld%d", xs + i, ys + i, cs + i);
			xs[i] *= 2;	// 乘2避免待会儿除法产生误差
			ys[i] *= 2;
		}
		for (int i = 0; i < n; ++i)
		{
			X[i * 2] = xs[i] - W;
			X[i * 2 + 1] = xs[i] + W;
			Y[i * 2] = ys[i] - H;
			Y[i * 2 + 1] = ys[i] - 1 + H;
		}
		sort(X, X + n * 2);	// 待会儿进行坐标压缩
		sort(Y, Y + n * 2);    // 为lower_bound做准备
		for (int i = 0; i < n; ++i)
		{
			event[i * 2] = 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 * 2 + 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++)
		{	
			add(event[i].second.first, event[i].second.second, event[i].first.second, 1, 0, n * 2);
			ans = max(ans, node_max[1]);
		}
		printf("%d\n", ans);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2482 Stars in Your Window 题解 《挑战程序设计竞赛》