UVA1398 Meteor 扫描线

还是搬一下lrj蓝皮书的翻译吧:

给定一个矩形, 左下角为(0, 0),右上角为((w,h)), 有(n)个流星, 每个流星有初始位置((x,y))和横向的移动速度(a), 纵向的移动速度(b), (若为整数是向上, 右, 若为负数是向下, 左). 假设(p)是初始位置, (v)为速度, 在时刻(t(t >= 0))的位置就是(p + vt).

求出在某一个时刻矩形内最多的流星的数量, 在矩形边缘的流星不算.(n <= 1e5).

扫描线.

这个题第一眼看上去并没有什么思路.阅读lrj的书后, 我们可以把问题转化成这样:

每个流星(i)经过矩形会有一个时间段((L_i, R_i)), 注意是开区间. 这样数轴上将会出现(i)条线段, 我们要找一个时刻(t),也就是数轴上找一个点, 使最多的线段包含它.

找这个点肯定不能枚举, 那么我们需要用到扫描线算法.

我们把"碰到左端点", "碰到右端点"都看作是一个事件, 然后按时间的出现顺序排序, 如果两个事件的出现时间一样, 那么把 "碰到右端点"的事件排在前面, 一定要这么排, 不然会错.

然后遍历每个事件, 对于事件一就让答案加一, 对于事件二就让答案减一.

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
	long long s = 0, f = 1; char ch;
	while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
	return s * f;
}

const int N = 2e5 + 5;
int n, w, h, cnt, res, ans;
double L, R;
struct LINE { 
	double p; int f; 
	LINE() {} LINE(double x, int z) { p = x; f = z;}
} line[N]; 

void make_line(int x, int a, int w, double &L, double &R) {
	if(a == 0) { if(x <= 0 || x >= w) R = L - 1; return ; }
	else if(a > 0) {
		L = max(L, -1.0 * x / a); R = min(R, 1.0 * (w - x) / a); return ;
	}
	else {
		L = max(L, 1.0 * (w - x) / a); R = min(R, -1.0 * x / a); return ; 
	}
}

int cmp(LINE a, LINE b) { return a.p == b.p ? a.f < b.f : a.p < b.p; } 

int main() {

	for(int T = read(); T ; T --) {
		w = read(); h = read(); n = read(); cnt = ans = res = 0;
		for(int i = 1, x, y, a, b;i <= n; i++) {
			x = read(), y = read(), a = read(), b = read();
			L = 0; R = 1e9;
			make_line(x, a, w, L, R); make_line(y, b, h, L, R);
			if(R > L) line[++ cnt] = LINE(L, 1), line[++ cnt] = LINE(R, -1);
		}
		sort(line + 1, line + cnt + 1, cmp);
		for(int i = 1;i <= cnt; i++) {
			if(line[i].f == 1) res ++, ans = max(ans, res);
			else res --;
		}
		printf("%d
", ans);
	}
	
	return 0;
}