UVA之1398 - Meteor

【题目】

The famous Korean internet company nhn has provided an internet-based photo service which allows The famous Korean internet company users to directly take a photo of an astronomical phenomenon in space by controlling a high-performance telescope owned by nhn. A few days later, a meteoric shower, known as the biggest one in this century, is expected. nhn has announced a photo competition which awards the user who takes a photo containing as many meteors as possible by using the photo service. For this competition, nhn provides the information on the trajectories of the meteors at their web page in advance. The best way to win is to compute the moment (the time) at which the telescope can catch the maximum number of meteors.

You havenmeteors, each moving in uniform linear motion; the meteorm_imoves along the trajectoryp_i+t×v_iover timet, wheretis a non-negative real value,p_iis the starting point ofm_iandv_iis the velocity ofm_i. The pointp_i= (x_i,y_i)is represented byX-coordinatex_iandY-coordinatey_iin the(X,Y)-plane, and the velocityv_i= (a_i,b_i)is a non-zero vector with two componentsa_iandb_iin the(X,Y)-plane. For example, ifp_i= (1, 3)andv_i= (-2, 5), then the meteorm_iwill be at the position (0, 5.5) at timet= 0.5becausep_i+t×v_i= (1, 3) + 0.5×(-2, 5) = (0, 5.5). The telescope has a rectangular frame with the lower-left corner (0, 0) and the upper-right corner(w,h). Refer to Figure 1. A meteor is said to be in the telescope frame if the meteor is in the interior of the frame (not on the boundary of the frame). For exam! ple, in Figure 1,p₂,p₃,p₄, andp₅cannot be taken by the telescope at any time because they do not pass the interior of the frame at all. You need to compute a time at which the number of meteors in the frame of the telescope is maximized, and then output the maximum number of meteors.

Input

Your program is to read the input from standard input. The input consists ofTtest cases. The number of test casesTis given in the first line of the input. Each test case starts with a line containing two integerswandh(1w,h100, 000), the width and height of the telescope frame, which are separated by single space. The second line contains an integern, the number of input points (meteors),1n100, 000. Each of the nextnlines contain four integersx_i,y_i,a_i, andb_i;(x_i,y_i)is the starting pointp_iand(a_i,b_i)is the nonzero velocity vectorv_iof thei-th meteor;x_iandy_iare integer values between -200,000 and 200,000, anda_iandb_iare integer values between -10 and 10. Note that at least one ofa_iandb_iis not zero. These four values are separated by single spaces. We assume that all starting pointsp_iare distinct.

Output

Your program is to write to standard output. Print the maximum number of meteors which can be in the telescope frame at some moment.

Sample Input

2 
4 2 
2 
-1 1 1 -1 
5 2 -1 -1 
13 6 
7 
3 -2 1 3 
6 9 -2 -1 
8 0 -1 -1 
7 6 10 0 
11 -2 2 1 
-2 4 6 -1 
3 2 -5 -1

Sample Output

1 
2

【分析】

不难发现，流星的轨迹是没有直接意义的，有意义的只是每个流星在照相机视野内出现的时间段。换句话说，我们把本题抽象为这样一个问题：给出n个开区间(Li,Ri)，你的任务是求出一个数t，使得包含它的区间数最多（为什么是开区间呢？请读者思考）。开区间(Li,Ri)是指所有满足Li<x<Ri的实数x的集合。

把所有区间画到平行于数轴的直线上（免得相互遮挡，看不清楚），然后想象有一条竖直线从左到右进行扫描，则问题可以转化为：求扫描线在哪个位置时与最多的开区间相交，如图所示。

不难发现，当扫描线移动到某个区间左端点的“右边一点点”时最有希望和最多的开区间相交（想一想，为什么）。为了快速得知在这些位置时扫描线与多少条线段相交，我们再一次使用前面提到的技巧：维护信息，而不是重新计算。

我们把“扫描线碰到一个左端点”和“扫描线碰到一个右端点”看成是事件（event），则扫描线移动的过程就是从左到右处理各个事件的过程。每遇到一个“左端点事件”，计数器加1；每遇到一个“右端点事件”，计数器减1。这里的计数器保存的正是我们要维护的信息：扫描线和多少个开区间相交，如图所示。

这样，我们可以写出这样一段伪代码。

将所有事件按照从左到右排序

while(还有未处理的事件){

选择最左边的事件E

if(E是“左端点事件”){cnt++;if(cnt>ans)ans=cnt;}//更新计数器和答案

elsecnt--;//一定是“右端点事件”

}

这段伪代码看上去挺有道理，但实际上暗藏危险：如果不同事件的端点相同，那么哪个排在前面呢？考虑这样一种情况——输入是两个没有公共元素的开区间，且左边那个区间的右端点和右边那个区间的左端点重合。在这种情况下，两种排法的结果截然不同：如果先处理左端点事件，执行结果是2；如果先处理右端点事件，执行结果是1。这才是正确答案。

这样，我们得到了一个完整的扫描算法：先按照从左到右的顺序给事件排序，对于位置相同的事件，把右端点事件排在前面，然后执行上述伪代码的循环部分。如果你对这个冲突解决方法心存疑虑，不妨把它理解成把所有区间的右端点往左移动了一个极小（但大于0）的距离。

【代码】

/*********************************
*   日期：2014-5-12
*   作者：SJF0115
*   题号: 1398 - Meteor
*   地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4144
*   来源：UVA
*   结果：Accepted
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

#define N 100010

//确定区间的左右端点
void IntervalRL(int x,int a,int w,double& L,double& R){
    if(a == 0){
        //0 < x < w
        if(x <= 0 || x >= w){
            //无解
            R = L - 1;
        }
    }
    // -x/a < t < (w-x)/a
    else if(a > 0){
        L = max(L,-(double)x/a);
        R = min(R,(double)(w - x)/a);
    }
    // (w-x)/a < t < -x/a
    else if(a < 0){
        L = max(L,(double)(w - x)/a);
        R = min(R,-(double)x/a);
    }
}
//区间
struct Inter{
    //坐标位置
    double x;
    //判断是左端点还是右端点
    int type;
    //重载 <
    bool operator <(const Inter& inter)const{
        return x < inter.x || (x == inter.x && type > inter.type);
    }
}Inters[N*2];

int main(){
    int T,w,h,n,i,x,y,a,b;
    //freopen("C:\\Users\\wt\\Desktop\\acm.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        int num = 0;
        //相机坐标
        scanf("%d%d%d",&w,&h,&n);
        for(i = 0;i < n;i++){
            double L = 0,R = 1e9;
            //x,y初始位置 a,b速度
            scanf("%d%d%d%d",&x,&y,&a,&b);
            //a b 不能同时为0
            if(a == 0 && b == 0){
                break;
            }
            //确定区间的左右端点
            IntervalRL(x,a,w,L,R);
            IntervalRL(y,b,h,L,R);
            //形成一个区间
            if(L < R){
                Inters[num].x = L;
                Inters[num++].type = 0;
                Inters[num].x = R;
                Inters[num++].type = 1;
            }//if
        }//for
        //排序
        sort(Inters,Inters+num);
        int cur = 0;
        int maxNum = 0;
        for(i = 0;i < num;i++){
            if(Inters[i].type == 0){
                cur++;
                maxNum = max(maxNum,cur);
            }
            else{
                cur--;
            }
        }//for
        printf("%d\n",maxNum);
    }//while
    return 0;
}