收集金币

 3 Sec 131071 KB |  显示标签
717
通过提交

题目描述

有一个矩阵,边界是[0,w](w>0)
刚开始时,你可以在(0,0)到(0,w)线段上的任意一个位置。
你在y轴方向的速度必须是一个正数
你在x轴方向的速度大小与y轴方向的速度大小存在一定的联系。
满足−vy/r<=vx<=vy/r,r是常量
你可以任意改变y轴速度,但是一定不能跑出矩阵(可以恰好在矩阵边界上)
终点在y = h,现在你要从y = 0通过矩阵到达y = h
为了增加游戏乐趣,跑道上还有许多金币。问最多收集多少金币。

输入格式

有多组测试数据
每一组测试数据,第一行有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枚金币的坐标

输出格式

每组测试数据输出能收集的最多金币数

样例输入 #1

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

样例输出 #1

3
3
 上传者
coach
 创建时间
2018-06-01 20:21
 修改时间
2018-06-03 19:53