分析
本题可以抽象成一个问题:给定$n$个开区间$(L_i,R_i)$,然后求出一个数$t$,使得包含它的区间数最多。
这样就可以应用扫描线思想,将扫描线碰到一个左端点和扫描线碰到一个右端点看成一个事件,然后给每个事件按左端点从左到右的顺序排序,如果左端点相同,那就按右端点小的在前面,然后移动扫描线,每碰到一个左端点,计数器加$1$,碰到一个右端点计数器减$1$。
代码
#include<cstdio>
#include<algorithm>
using std::max;using std::min;using std::sort;
const int MAXN = 100000 + 6;
class Event{
public:
int x,type;
bool operator < (const Event &a) const{return x < a.x || (x == a.x && type > a.type);}
};Event ev[MAXN];
void update(int x,int a,int w,int &L,int &R){
if(a == 0){if(x <= 0 || x >= w) R = L - 1;}
else if(a > 0) L = max(L,-x * 2520),R = min(R,(w - x) * 2520 / a);
else L = max(L,(w - x) * 2520 / a),R = min(R,-x * 2520 / 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);
int L = 0,R = (int)1e9;
update(x,a,w,L,R);
update(y,b,h,L,R);
if(R > L) ev[e++] = (Event){L,0},ev[e++] = (Event){R,1};
}
sort(ev,ev + e);
int cnt = 0,ans = 0;
for(int i = 0;i < e;i++){
if(ev[i].type == 0) ans = max(ans,++cnt);
else cnt--;
}
printf("%d\n",ans);
}
return 0;
}