演算法競賽入門經典訓練指南打卡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;  }