蒟蒻的题解，好像都是这么写的吧

TongLi_Galaxy · 2019-02-23 22:54:45 · 题解

这个题用扫描线做！你自己画一张图，已知速度和起点，做矢量运算，算出来每一颗流星会在什么时候飞进镜头，会在什么时候飞出镜头，并在时间轴上标记出来。遇见进入镜头一个流星就计数器++，离开镜头一个计数器--。

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

struct lin{
    double x;
    int type;
    bool operator<(const lin &a) const{
        return x<a.x||(x==a.x&&type>a.type);
    }
}line[200020];

void updat(int x,int a,int w,double &l,double &r){
    double L=0,R=0; //计算每一颗流星进入和离开镜头的时刻
    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(){
    int t;
    scanf("%d",&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;
            updat(x,a,w,l,r);
            updat(y,b,h,l,r);
            if(r>l){ //把时刻记在时间线上
                line[e]=(lin){l,0},e++;
                line[e]=(lin){r,1},e++;
            }
        }
        sort(line,line+e);
        int cnt=0,ans=0;
        for(int i=0;i<e;i++){ //扫描线代码
            if(line[i].type==0){
                cnt++; //有流星进入计数器++
                ans=max(ans,cnt); //求最大值
            }
            else cnt--; //有流星离开就计数器--
        }
        printf("%d\n",ans);
    }
    return 0;
}