原题链接：Meteor - UVALive 3905 - Virtual Judge
Meteor流星
直接上代码：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;const int maxn = 1e5 + 10;struct Event {double x;int type;bool operator < (const Event& a) const {return (x < a.x) || (x == a.x && type > a.type); //先处理右端点}
} events[maxn * 2];void update(int x, int a, int w, double& L, double& R) { //update写得很巧妙if (a == 0) { if (x <= 0 || x >= w) R = L - 1; //R一旦成为负的，就只能是负的了}else if (a > 0) { //关于R.L可以多想一下L = max(L, -(double) x / a); // L最小为0R = min(R, (double)(w - x)/ a); //R可以为负的} //L得是这个区间x和y能进入矩形区域的最大值，R是最小值else {L = max(L, (double)(w - x) / a); //速度正负要区分R = min(R, -(double)x / a); //自己画数轴看}
}int main() {int t;cin >> t;while (t--) {int w, h, n, x, y, a, b, e = 0;cin >> w >> h >> n;for (int i = 0; i < n; i++) {cin >> x >> y >> a >> b;double L = 0, R = 1e9; update(x, a, w, L, R); //对横坐标找到区间update(y, b, h, L, R); //对纵坐标找到区间if (L < R) {events[e++] = Event{ L, 0 }; //左右端点分别设为一个Eventevents[e++] = Event{ R, 1 };}}sort(events, events + e); //struct类型的sortint ans = 0, cnt = 0;for (int i = 0; i < e; i++) {if (events[i].type == 0) cnt++;else cnt--;ans = max(ans, cnt);}cout << ans << endl;}return 0;
}注意：
1.流星的轨迹是没有直接意义的，有意义的只是每个流星在照相机视野内出现的时间段；
2.时间段是开区间，因为在矩形的边上不算。如果一开始流星就在矩形内，那么肯定会有一段时间是还留在矩形中的，所以开区间没有问题；
3.左端点和右端点分别列为两个事件，在sort之中和最后的cnt加减之中他们彼此是相互独立的，没有什么关联，但是在算每一段区间的L和R的时候，必须是L < R 才会有这段区间，才会有左端点和右端点；
4.如果一个左端点事件和一个右端点事件重合，那么想想看，右端点是不会有为0的情况的，所以一定是一个流星准备进入，一个流星刚好出去，他们现在都在边缘线上，所以不会同时出现在矩形区域里，所以应该把要出去的这个右端点事件放在左端点事件前面，就像Event里面的<重载那个意思。