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

• 2020 年 2 月 18 日
• 筆記

题解: 转换一下问题.每一个流星在矩形照相机中的时间段是确定的(如果可以进入矩形照相机).假设在这n个流星中有k个流星在一定时间段可以照到.第$i$个流星能照到的时间段是$(L_i, R_i) 1 leq i leq k. 1 leq k leq n.$所以我们只要求出这$k$个开区间的最大交集的数量.就是某一时刻最多有多少个区间有交集. 假设我们已经计算出这k个开区间.考虑下面的算法:

1. 每一个区间有两个端点.将每一个区间的左右端点分别看作一个事件.按照坐标优先级第一从小到大.坐标相同的按照右端点优先原则排序.
2. 有一个扫描线.一个计数器cnt=0.答案保存ans=0.从小到大开始扫描事件.当遇到当前事件是左端点时.cnt加上1.更新ans取大.当遇到当前事件是右端点时.cnt减去1.
3. 这样扫描完就得到答案.复杂度$O(log(n))$

计算区间:

#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;  }