问题1926--导弹发射

1926: 导弹发射

时间限制: 1 Sec  内存限制: 128 MB
提交: 136  解决: 14
[状态] [讨论版] [提交] [命题人:]
题目描述
Alpha 机构研发出一种新型智能导弹,它能够在雷达检测到的区域内,选择一条前进的路径,击破路径上所有的目标物。雷达位于(0,0)处,它能够检测到两条射线之间的区域(不妨设在第一象限)。
导弹一开始置放在(0,0)处,它可以在雷达能检测到的区域内先选择一个目标物击破,然后再继续前进,选择另一个目标物击破。注意,导弹不能沿着这两条射线前进,当然也不能停在原地。
可以假设,导弹一旦发射,其能量无比大,前进的路径无限长。
已知雷达能够检测到区域,其射线 1:ax-by=0 和射线 2:cx-dy=0。Alpha 机构的总指挥希望在发现目标群的第一时刻,计算出一条可以击破最多目标物的路径。

输入
第一行: T 表示以下有 T 组测试数据(1≤T ≤8)
对每组测试数据:
第 1 行: n 表示目标物的个数
第 2 行: a b c d 代表两条射线的斜率分别是 a/b 和 c/d。
接下来有 n 行,每行 2 个正整数 xi yi 即第 i 个目标物的坐标。
(1) n<=10^5 0<=a, b, c, d<=10^5 a 和 b 不会同时为 0,c 和 d 不会同时为 0;
(2) 0<= xi , yi <=10^6 i=1,…..,n

输出
每组测试数据,输出占一行,即导弹能击破的最多目标数。

样例输入 Copy
1
15
1 3 2 1
3 1
6 2
4 2
2 5
4 5
6 6
3 4
1 6
2 1
7 4
9 3
5 3
1 3
15 5
12 4
样例输出 Copy
4
来源/分类