扫描线法。
将流星出现在相机里的时间转化成线段，离散化端点后，扫描何时出现的流星最多。注意边界的不算，所以要先减右端点再加左端点
1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #define LL long long 8 using namespace std; 9 const int mxn=100010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 int T; 17 int n,w,h; 18 struct node{ 19 int v,t; 20 }c[mxn<<1];int cnt=0; 21 int cmp(node a,node b){ 22 if(a.v==b.v)return a.t>b.t; 23 return a.v<b.v; 24 } 25 //int h1[mxn],h2[mxn],w1[mxn],w2[mxn]; 26 int L,R; 27 void init(int a,int x,int w){ 28 if(!a){ if(x<=0 || x>=w)R=L-1; } 29 else if(a>0){ 30 L=max(L,-x*2520/a); 31 R=min(R,(w-x)*2520/a); 32 } 33 else{ 34 L=max(L,(w-x)*2520/a); 35 R=min(R,-x*2520/a); 36 } 37 return; 38 } 39 int main(){ 40 T=read(); 41 int i,j; 42 int x,y,a,b; 43 while(T--){ 44 cnt=0;//init 45 w=read();h=read();n=read(); 46 for(i=1;i<=n;i++){ 47 x=read();y=read();a=read();b=read(); 48 L=0,R=0x7f7f7f7f; 49 init(a,x,w);init(b,y,h); 50 if(R>L){ 51 c[++cnt].v=L;c[cnt].t=0; 52 c[++cnt].v=R;c[cnt].t=1; 53 } 54 } 55 sort(c+1,c+cnt+1,cmp); 56 int ans=0,ct=0; 57 for(i=1;i<=cnt;i++){ 58 if(!c[i].t){//进入 59 ++ct; 60 ans=max(ans,ct); 61 } 62 else --ct; 63 } 64 printf("%d ",ans); 65 } 66 return 0; 67 }