蒟蒻的题解，好像都是这么写的吧
TongLi_Galaxy
2019-02-23 22:54:45
这个题用扫描线做！你自己画一张图，已知速度和起点，做矢量运算，算出来每一颗流星会在什么时候飞进镜头，会在什么时候飞出镜头，并在时间轴上标记出来。遇见进入镜头一个流星就计数器++，离开镜头一个计数器--。
```cpp
#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;
}
```