LA 3905 Meteor / 区间扫描

求哪一时刻 框框里的点最多 每个点在做运动（在边框上不算）

求出每个点经过框框的区间 在2维坐标系以x表示 是开区间 因为区间边上不算

假设有一条竖线从左到右扫描过去 也就是求哪一时刻扫描线相交的区间最多

可以设cnt = 0每遇到左区间++右区间--求最大的cnt 然后一个区间右端点与一个区间的左区间相同 要先算右区间因为是开区间

书上的代码

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

const int maxn = 100010;
struct Event
{
	double x;
	int type;
	bool operator < (const Event& a) const
	{
		return x < a.x || (x == a.x && type > a.type);
	}
}event[maxn*2];

void update(int x, int a, int w, double& l, double& r)
{
	if(a == 0)
	{
		if(x <= 0 || x >= w)
			r = l - 1;
	}
	else if(a > 0)//0 < x+at < w <=> t > -x/a && t < (w-x)/a
	{
		l = max(l, -(double)x/a);
		r = min(r, (double)(w-x)/a);
	}
	else if(a < 0)//0 < x+at < w <=> t < -x/a && t > (w-x)/a
	{
		l = max(l, (double)(w-x)/a);
		r = min(r, -(double)x/a);
	}
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int w, h, n, e = 0;
		scanf("%d %d %d", &w, &h, &n);
		for(int i = 0; i < n; i++)
		{
			int x, y, a, b;
			scanf("%d %d %d %d", &x, &y, &a, &b);
			double l = 0, r = 1e9;
			update(x, a, w, l, r);
			update(y, b, h, l, r);
			if(l < r)
			{
				event[e++]= (Event){l, 0};
				event[e++]= (Event){r, 1};
			}
		}
		sort(event, event+e);
		int cnt = 0;
		int ans = 0;
		for(int i = 0; i < e; i++)
		{
			if(event[i].type == 0)
				cnt++;
			else
				cnt--;
			ans = max(ans, cnt);
		}
		printf("%d\n", ans);
	}
	return 0;
}

LA 3905 Meteor / 区间扫描

原文：http://blog.csdn.net/u011686226/article/details/18714785