【题解】LA 3905【Meteor】

分析

本题可以抽象成一个问题：给定$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;
}