uva 1398 - Meteor

点击打开链接uva 1398

思路：扫描法
分析：
1 不难发现，流星的轨迹是没有用的，有意义的只是每个流星在照相机视野内出现的时间段
2 那么我们就可以通过去求出没个流星在矩形内的时间段，然后利用扫描法去求。
具体见刘汝佳<<训练指南46页>>

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100010;

struct Event{
    double x;
    int type;
    bool operator<(const Event& rhs)const{
         return x < rhs.x || x == rhs.x && type == 1; 
    }

};
Event events[MAXN*2];

//求时间段
void update(int x , int a , int w , double&left , double& right){
     if(a == 0){
       if(x <= 0 || x >= w)
           right = left-1;
     }
     else if(a > 0){
         left = max(left , -x*1.0/a); 
         right = min(right , (w-x)*1.0/a);
     }
     else{
         left = max(left , (w-x)*1.0/a);     
         right = min(right , -x*1.0/a);
     }
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
        int w , h , n , pos = 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 left = 0 , right = 1e9;
           update(x , a , w , left , right);//水平风向求时间段
           update(y , b , h , left , right);//竖直方向求时间段
           if(right > left){
              events[pos++] = (Event){left , 0};//左端点事件
              events[pos++] = (Event){right , 1};//右端点事件
           }
        }
        int ans = 0;
        int cnt = 0;
        for(int i = 0 ; i < pos ; i++){
           if(events[i].type == 0) //碰到左端点更新cnt和ans
               ans = max(ans , ++cnt);
           else
               cnt--;
        }
        printf("%d\n" , ans);
    }
    return 0;
}