例题20 流星(LA 3905)

给你一个矩形,还有n个点初始位置和速度,求矩形内包含流星最多的时刻,注意,矩形的边上不算照到. 模型建立:把t看作一个变量,那么对于每个流星 x x x来说,它在矩形出现的时间可以简化为 [ L x , R x ] [L_x,R_x] [Lx​,Rx​],那么问题转化为从左边往后边扫求某个时刻,该竖线 t t t与最多区间相交. 注意,要先处理 R x R_x Rx​的事件,因为在那一时刻,该流星已经消失看不见了. 观看蓝书代码后,技巧又学到了.因为我们只关注这个区间的左右端点 L X , R x L_X,R_x LX​,Rx​,只用把他们存进去就行.

/*
*/
#include
using namespace std;
typedef long long ll;
const int maxn = 1e5+2;
const int INF = 1e9+7;
typedef pair pii;
void update(int x,int a,int w,double &L,double &R){
	if(a==0){
		//该分量没有速度
		if(x=w) R = L - 1;  
	}
	else if(a>0){
		L = max(L,(double)(0-x)/a);//只有x在负半轴才有意义.
		R = min(R,(double)(w-x)/a); 
	}
	else{
		L = max(L,(double)(w-x)/a);
		R = min(R,(double)(0-x)/a);
	}
}
struct Node{
	double dis;int type;
	bool operator >T;
	while(T--){
		int n,w,h;
		cin>>w>>h>>n;
		vector vec;
		for(int i=0;i>x>>y>>a>>b;
			double L=0;double R= INF;
			update(x,a,w,L,R);
			update(y,b,h,L,R);
			if(R>L){
				vec.push_back({R,1});
				vec.push_back({L,0});
			}
		}
		sort(vec.begin(),vec.end());
		int cnt = 0;int ans = 0;
		for(auto it : vec){
			if(it.type==1) cnt--;
			else cnt++,ans=max(cnt,ans);
		}
		cout