题意
请参考LRJ白书第一章例题20
思路
扫描线。
这个题分为两部分,首先是要求出每一颗流星划过取景框的时间区间,这一步反而是这个题最复杂的地方,因为要讨论许多种情况,具体的讨论策略可以参考下面的代码。
求出来所有的区间之后,问题转化为选出一条线,使得这条线穿过的区间最多,这里就是扫描线算法派上用场的时候了。其实实现很简单,就是对于每个区间的两个端点,分别创建一个表示起始的事件和一个表示结束的事件,然后把所有事件按照出现的时间排序,接下来从小往大检查,遇到开始事件的时候计数器+1,遇到结束事件的时候计数器-1.
这里有一个问题,如果开始事件和结束事件恰好位于同一时点,怎么办?注意到我们的区间都是开的,这样我们只要优先处理结束事件,就不会导致解偏大了(这里面的逻辑需要自己试着理解一下)。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> #include <cassert> using namespace std; int w,h; int n; struct Event { int t; int dir; bool operator < (const Event &b) const { if(t == b.t) { return dir < b.dir; } return t < b.t; } }; vector<Event> event; int main() { int caseCnt; scanf(" %d",&caseCnt); for(int d = 1; d <= caseCnt; d++) { scanf(" %d %d %d",&w,&h,&n); event.clear(); for(int i = 1; i <= n; i++) { double x,y,a,b; scanf(" %lf %lf %lf %lf",&x,&y,&a,&b); bool fail = false; int l = 0,r = 0x3f3f3f3f; if(a != 0) { //Left Side int tls = -(x*2520/a); //Right Side int trs = (w-x)*2520/a; if(a > 0){ l = max(l,tls); r = min(r,trs); }else{ l = max(l,trs); r = min(r,tls); } }else{ if(x <= 0 || x >= w){ fail = true; } } if(b != 0) { //Upper Side int tus = (h-y)*2520/b; //Down Side int tds = -(y*2520/b); if(b > 0){ l = max(l,tds); r = min(r,tus); }else{ l = max(l,tus); r = min(r,tds); } }else{ if(y <= 0 || y >= h){ fail = true; } } Event tmp; if(!fail && l < r){ tmp.t = l; tmp.dir = 1; event.push_back(tmp); tmp.t = r; tmp.dir = -1; event.push_back(tmp); } } sort(event.begin(),event.end()); int cur = 0; int res = 0; for(int i = 0; i < event.size(); i++) { cur += event[i].dir; res = max(res,cur); } printf("%d\n",res); } return 0; } |