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

---

emm.最近有点小烦躁.今年还只能打两场了.青岛和沈阳.想要拿牌子.题目不知如何刷起.太多了呀.自己太菜了呀.所以来一个打卡系列吧.打卡刘汝佳<<算法竞赛 入门经典 训练指南>>. so. 打卡day1.

Meteor UVALive - 3905

题目大意:
有一个矩形照相机.矩形照相机照到的范围是$(0,0)$到$(w,h)$.有$n$个流星.第i个流星的初始坐标$(x_i, y_i)$,速度$(a_i, b_i)$.所以.$t(t >= 0)$时刻第$i$个流星的位置就是$(x_{ti}, y_{ti}) = (x_i, y_i) + t*(a_i, b_i).$求某一时刻矩形照相机最多可以照到的流星数量.(在边界上照到的不算)

题解:
转换一下问题.每一个流星在矩形照相机中的时间段是确定的(如果可以进入矩形照相机).假设在这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;
}