收集金币
3 Sec 131071 KB |
7 | 17 |
通过 | 提交 |
题目描述
有一个矩阵,边界是[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