题目链接
https://vjudge.net/problem/UVALive-3905
题目
The famous Korean internet company 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 . A few days later, a
meteoric shower, known as the biggest one in this century, is expected. 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, 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 have n meteors, each moving in uniform linear motion; the meteor mi moves along the trajectory
pi + t × vi over time t, where t is a non-negative real value, pi
is the starting point of mi and vi
is
the velocity of mi
. The point pi = (xi
, yi) is represented by X-coordinate xi and Y -coordinate yi
in
the (X, Y )-plane, and the velocity vi = (ai
, bi) is a non-zero vector with two components ai and bi
in the (X, Y )-plane. For example, if pi = (1, 3) and vi = (?2, 5), then the meteor mi will be at the
position (0, 5.5) at time t = 0.5 because pi + t × vi = (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 example, in Figure 1, p2, p3, p4, and p5 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.
Figure 1
Input
Your program is to read the input from standard input. The input consists of T test cases. The
number of test cases T is given in the first line of the input. Each test case starts with a line containing
two integers w and h (1 ≤ w, h ≤ 100, 000), the width and height of the telescope frame, which are
separated by single space. The second line contains an integer n, the number of input points (meteors),
1 ≤ n ≤ 100, 000. Each of the next n lines contain four integers xi
, yi
, ai
, and bi
; (xi
, yi) is the starting
point pi and (ai
, bi) is the nonzero velocity vector vi of the i-th meteor; xi and yi are integer values
between -200,000 and 200,000, and ai and bi are integer values between -10 and 10. Note that at least
one of ai and bi
is not zero. These four values are separated by single spaces. We assume that all
starting points pi are 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
题意
给定一个矩形框，矩形框的左下角为(0,0),右上角（w,h)。再给定n个点的初始位置(x,y)和速度（a,b)，问最多有多少个点同时在矩形框内（在边界线上不算）。
分析
对每一个点，求出其在矩形框内的时间区间（L,R）。把所有区间画到平行于x轴的直线上，然后用一个竖线从左到右进行扫描。在扫描的过程中，每遇到一个区间的左端点，当前同在矩形框内的点的总数sum++；每遇到一个区间的右端点，sum–。又因为时间区间是开区间，所以同时扫描到左端点和右端点时要先处理右端点。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3fusing namespace std;const int maxn=1e5+100;struct event
{double t; //时刻int type; //0表示开始，1表示结束bool operator<(const event &o)const{return t<o.t ||(t==o.t&&type>o.type);}
}e[maxn<<1];//解不等式 0< x+at <w
void updata(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) //-x <at< w-x,同除以一个正数，小于号不变{L=max(L,-(double)x/a); //max是为了两个时间区间取交集R=min(R,(double)(w-x)/a);}else //小于号变号{L=max(L,(double)(w-x)/a);R=min(R,-(double)x/a);}
}int main()
{int T,cnt; //测试组数scanf("%d",&T);while(T--){int h,w,n;cnt=0;scanf("%d%d%d",&w,&h,&n);int x,y,a,b;for(int i=0;i<n;i++){double L=0,R=INF;scanf("%d%d%d%d",&x,&y,&a,&b);updata(x,a,w,L,R); //L表示开始时刻，R表示结束时刻updata(y,b,h,L,R); //两个区间取交集if(R>L) //是否有解{e[cnt++]=(event){L,0};e[cnt++]=(event){R,1};}}sort(e,e+cnt);int sum=0,ans=0;for(int i=0;i<cnt;i++){if(!e[i].type)ans=max(ans,++sum);else--sum;}printf("%d\n",ans);}return 0;
}