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,右端点事件为1 bool 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; }