扫描线，注意这个题目要求的是开区间；
1 #include<cstdio> 2 #include<algorithm> 3 #define maxn 100009 4 using namespace std; 5 6 void update(int x,int a,int w,double& l,double& r) 7 { 8 if(a==0) 9 { 10 if(x<=0||x>=w)r=l-1; 11 } 12 else if(a>0) 13 { 14 l=max(l,-(double)x/a); 15 r=min(r,(double)(w-x)/a); 16 } 17 else 18 { 19 l=max(l,(double)(w-x)/a); 20 r=min(r,-(double)x/a); 21 } 22 } 23 24 struct eve 25 { 26 double x; 27 int type; 28 eve(double x=0,int type=0):x(x),type(type) {} 29 bool operator<(const eve& a)const 30 { 31 return x<a.x||(x==a.x&&type>a.type); 32 } 33 } events[maxn*2]; 34 35 36 int main() 37 { 38 int t,x,y,a,b,w,h,n; 39 scanf("%d",&t); 40 while(t--) 41 { 42 int e=0; 43 scanf("%d%d%d",&w,&h,&n); 44 for(int i=0; i<n; i++) 45 { 46 scanf("%d%d%d%d",&x,&y,&a,&b); 47 double l=0,r=10e9; 48 update(x,a,w,l,r); 49 update(y,b,h,l,r); 50 if(r>l) 51 { 52 events[e++]=eve(l,0); 53 events[e++]=eve(r,1); 54 } 55 } 56 sort(events,events+e); 57 int cnt=0,ans=0; 58 for(int i=0; i<e; i++) 59 { 60 if(events[i].type==0)ans=max(ans,++cnt); 61 else cnt--; 62 } 63 printf("%d ",ans); 64 } 65 return 0; 66 }