LA 3905

【类型】

区间扫描,  抽象成事件来做的区间扫描

【题解】

蓝书P45

另一个更详细的blog

代码中难懂的部分都已经注释了.

【Code】

#include<bits/stdc++.h>
using namespace std;

//0<x+a*t<w
//0<x+a*t<w,0<y+b*t<h,  t>0
//起始坐标:(x,y) 速度:(a,b)
//x横坐标运动范围(0-w) y纵坐标运动范围(0-h)
//题目给的公式 在时刻t坐标:p+tv=(x,y)+(t*a,t*b)
//然后根据这个范围求出出现在镜框的范围内的时间区间,开区间
//因为出现在镜框上不算进入射程.
void update(int x,int a,int w,double &L,double &R){
    if(a==0){
        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);
    }
}

const int maxn=100000+10;
struct Event{
    double x;
    int type;//状态,0为右端点,1为左端点
    bool operator<(const Event &a)const{
        return x<a.x || (x==a.x && type>a.type);//先处理右端点
    }
}events[maxn*2];

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);
            //0<x+a*t<w,0<y+b*t<h,  t>0
            double L=0,R=1e9;//先开一个无穷大的区间
            update(x,a,w,L,R);
            update(y,b,h,L,R);
            if(R>L){//只把有效可进入镜框的点加入区间
                events[e++]=(Event){L,0};
                events[e++]=(Event){R,1};
            }
        }
        //排序区间,可以画图看下.
        sort(events,events+e);
        int cnt=0,ans=0;
        for(int i=0;i<e;++i){
            if(events[i].type==0)
                cnt++,ans=max(ans,cnt);
            else cnt–;
        }
        printf(“%d\n”,ans);
    }
    return 0;
}