算法竞赛入门经典训练指南打卡day1

#include <bits/stdc++.h>
using namespace std;


int T;
int w,h,n,a,b;

struct Event{
	double x;
	int type; // 0表示左端点.1表示右端点
	bool operator<(const Event& b)const{
		// 第一优先级.端点坐标从小到大.第二优先级.先处理右端点
		return x < b.x || (x == b.x && type > b.type); 
	}
};

// 计算到达边界的时间
void update(int x, int a, int w, double &L, double &R){
	/*
		x + t1*a > 0
		x + t2*a < w
	*/
	if(a == 0){
		if(x <= 0 || x >= w) R = L-1; // a是0.而且一开始就在外面
	} else if(a > 0){
		L = max(L, -(double)x/a);
		R = min(R, (double)(w-x)/a);
	} else {
		L = max(L, (double)(w-x)/a);
		R = min(R, -(double)x/a);
	}
}

int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0);
	int x,y;
	double L,R;
	cin >> T;
	while(T--){
		cin >> w >> h >> n;
		vector<Event> v;
		for(int i = 1; i <= n; ++i){
			cin >> x >> y >> a >> b;
			L = 0; R = 1e9;
			// 0 < x+t*a < w, 0 < y+t*a < h
			update(x, a, w, L, R);
			update(y, b, h, L, R);
			if(R > L){ // 区间成立
				// 加入左右端点
				v.push_back((Event){L, 0});
				v.push_back((Event){R, 1});
			}
		}
		sort(v.begin(), v.end()); // 排好序
		int ans = 0;
		int cnt = 0;
		for(auto &x : v){
			if(x.type == 0) { 
				++cnt; // 左端点的时候加上
				ans = max(ans, cnt);
			} else --cnt; // 右端点的时候减去
		}
		cout << ans << endl;
	}
	return 0;
}