卡丁车
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 65535/65535K (Java/Other)
Total Submission(s) : 6 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
这是一款十分经典的手机游戏。
在一个平面直角坐标系中,有一条带状且垂直x轴的跑道,跑道的边界分别是x = 0和x = w(w>0)
刚开始时,卡丁车初始位置可以是(0,0)到(0,w)线段上的任意一个位置。
卡丁车在x轴方向上能有速度,在y轴方向上也能有速度,但是y轴的速度的方向必须是y轴正方向,速度大小可以是任意的。
卡丁车在x轴方向的速度大小与y轴方向的速度大小存在一定的联系。
设vy表示在y轴正方向上的速度大小,vx表示x轴方向的速度大小。必须有-vy / r <= vx <= vy / r, r是常量
卡丁车能在任意位置任意改变y的速度,但是卡丁车一定不能跑出跑道(可以恰好在跑道边界上)
跑道的终点在y = h,现在卡丁车要从y = 0通过跑道到达y = h
为了增加游戏乐趣,跑道上还有许多金币。
那么问题来了,热爱打游戏的你,最多能收集到多少枚金币。
在一个平面直角坐标系中,有一条带状且垂直x轴的跑道,跑道的边界分别是x = 0和x = w(w>0)
刚开始时,卡丁车初始位置可以是(0,0)到(0,w)线段上的任意一个位置。
卡丁车在x轴方向上能有速度,在y轴方向上也能有速度,但是y轴的速度的方向必须是y轴正方向,速度大小可以是任意的。
卡丁车在x轴方向的速度大小与y轴方向的速度大小存在一定的联系。
设vy表示在y轴正方向上的速度大小,vx表示x轴方向的速度大小。必须有-vy / r <= vx <= vy / r, r是常量
卡丁车能在任意位置任意改变y的速度,但是卡丁车一定不能跑出跑道(可以恰好在跑道边界上)
跑道的终点在y = h,现在卡丁车要从y = 0通过跑道到达y = h
为了增加游戏乐趣,跑道上还有许多金币。
那么问题来了,热爱打游戏的你,最多能收集到多少枚金币。
Input
有多组测试数据
每一组测试数据,第一行有4个数,为n,r,w,h(1 <= n <= 1000, 1 <= r <= 10, 1 <= w, h <= 1000000000)
分别表示金币的个数,常量r的大小(具体见描述),跑道的边界以及跑道的终点
接下来n行,每一行有两个数xi, yi(0 <= xi <= w, 0 <= yi <= h),表示第i枚金币的坐标
每一组测试数据,第一行有4个数,为n,r,w,h(1 <= n <= 1000, 1 <= r <= 10, 1 <= w, h <= 1000000000)
分别表示金币的个数,常量r的大小(具体见描述),跑道的边界以及跑道的终点
接下来n行,每一行有两个数xi, yi(0 <= xi <= w, 0 <= yi <= h),表示第i枚金币的坐标
Output
每组测试数据输出能收集的最多金币数
Sample Input
5 1 10 10 8 8 5 1 4 6 4 7 7 9 5 1 100 100 27 75 79 77 40 93 62 41 52 45
Sample Output
3 3