数星星:夜空有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//////////////////////////////////
13892495 | hankcs | 2482 | Accepted | 1524K | 141MS | C++ | 2431B | 2015-02-16 01:09:08 |
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 2482 Stars in Your Window 题解 《挑战程序设计竞赛》