1.题目描述：点击打开链接
2.解题思路：本题实质上是求当若干个时间区间相交最多的时的个数。首先，求出每个流星落入方框内的时间段(L,R)（这里用开区间，，防止精度问题导致误差）。然后就相当于一道贪心法的题目了。定义时间线“碰到一个左端点”或“碰到一个右端点”为一个事件，那么每次遇到一个“左端点事件”，cnt++，并维护目前遇到的最大值；碰到“右端点事件”，cnt–。不过在排序的时候会遇到一个问题，当左端点相同但右端点不同时应当怎么排序？由于最先扫描到的右端点肯定是较小的那个，因此应该让右端点小的排在前面。这样便解决了本题。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;const int N = 100000 + 10;struct Event{double x;int type;//左端点事件为0，右端点事件为1bool operator <(const Event&a)const{return x<a.x || (x == a.x&&type>a.type);}}events[N*2];void update(int x, int a, int w, double&L, double&R)//解方程求时间段(L,R){if (!a){if (x <= 0 || x >= w)R = L – 1;}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("t.txt", "r", stdin);int T;cin >> T;while (T–){int w, h, n, e = 0;scanf("%d%d%d", &w, &h, &n);for (int i = 0; i < n; i++){int x, y, a, b;scanf("%d%d%d%d", &x, &y, &a, &b);double L = 0, R = 1e9;update(x, a, w, L, R);update(y, b, h, L, R);if (R>L){events[e++] = Event{ L, 0 };events[e++] = Event{ R, 1 };}}sort(events, events + e);int cnt = 0, ans = 0;for (int i = 0; i < e; i++){if (events[i].type == 0)ans = max(ans, ++cnt);else cnt–;}printf("%d\n", ans);}return 0;}
怎么能研究出炸药呢?爱迪生不经历上千次的来自失败，怎么能发明电灯呢?
