这样，我们可以写出这样一段伪代码。
将所有事件按照从左到右排序
while(还有未处理的事件) {
选择最左边的事件E
if(E是“左端点事件”) { cnt++; if(cnt > ans) ans = cnt; } //更新计数器和答案
else cnt--; //一定是“右端点事件”
}
这段伪代码看上去挺有道理，但实际上暗藏危险：如果不同事件的端点相同，那么哪个排在前面呢？考虑这样一种情况――输入是两个没有公共元素的开区间，且左边那个区间的右端点和右边那个区间的左端点重合。在这种情况下，两种排法的结果截然不同：如果先处理左端点事件，执行结果是2；如果先处理右端点事件，执行结果是1。这才是正确答案。
这样，我们得到了一个完整的扫描算法：先按照从左到右的顺序给事件排序，对于位置相同的事件，把右端点事件排在前面，然后执行上述伪代码的循环部分。如果你对这个冲突解决方法心存疑虑，不妨把它理解成把所有区间的右端点往左移动了一个极小（但大于0）的距离。
【代码】
/********************************* * 日期：2014-5-12 * 作者：SJF0115 * 题号: 1398 - Meteor * 地址：http://uva.onlinejudge.org/index.php option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4144 * 来源：UVA * 结果：Accepted **********************************/ #include#include #include #include using namespace std; #define N 100010 //确定区间的左右端点 void IntervalRL(int x,int a,int w,double& L,double& R){ if(a == 0){ //0 < x < w if(x <= 0 || x >= w){ //无解 R = L - 1; } } // -x/a < t < (w-x)/a else if(a > 0){ L = max(L,-(double)x/a); R = min(R,(double)(w - x)/a); } // (w-x)/a < t < -x/a else if(a < 0){ L = max(L,(double)(w - x)/a); R = min(R,-(double)x/a); } } //区间 struct Inter{ //坐标位置 double x; //判断是左端点还是右端点 int type; //重载 < bool operator <(const Inter& inter)const{ return x < inter.x || (x == inter.x && type > inter.type); } }Inters[N*2]; int main(){ int T,w,h,n,i,x,y,a,b; //freopen("C:\\Users\\wt\\Desktop\\acm.txt","r",stdin); scanf("%d",&T); while(T--){ int num = 0; //相机坐标 scanf("%d%d%d",&w,&h,&n); for(i = 0;i < n;i++){ double L = 0,R = 1e9; //x,y初始位置 a,b速度 scanf("%d%d%d%d",&x,&y,&a,&b); //a b 不能同时为0 if(a == 0 && b == 0){ break; } //确定区间的左右端点 IntervalRL(x,a,w,L,R); IntervalRL(y,b,h,L,R); //形成一个区间 if(L < R){ Inters[num].x = L; Inters[num++].type = 0; Inters[num].x = R; Inters[num++].type = 1; }//if }//for //排序 sort(Inters,Inters+num); int cur = 0; int maxNum = 0; for(i = 0;i < num;i++){ if(Inters[i].type == 0){ cur++; maxNum = max(maxNum,cur); } else{ cur--; } }//for printf("%d\n",maxNum); }//while return 0; }