← 返回题目列表

Codeforces · 249/D

D. 驴和星星

中文机器翻译题面 查看原题

晚上,驴子会和史莱克一起看星星。他们坐在一根圆木上,喝着茶,看着星空。天空悬挂在屋顶上方,就在烟囱后面。史莱克的星星在烟囱的右边,驴子的星星在左边。大多数时候,驴子只会数星星,所以他知道它们正好是n。这次他想要挑战。他想象了一个坐标系:他将坐标原点放在屋顶和烟囱的交点处,将 OX 轴指向左侧,沿屋顶指向左侧,OY 轴指向上方,沿烟囱指向上方(见图)。驴想象两条射线从轴原点发出,与 OX 轴成角度 α1 和 α2。

现在他选择严格位于这些光线之间的任何恒星。之后,他想象更多的光线从这颗恒星以与 OX 轴相同的角度 α1 和 α2 发出,并选择严格位于新光线之间的另一颗恒星。只要仍然有恒星,他就可以重复该操作,他可以​​在恒星发出的光线之间进行选择。

结果,驴得到了一串星星。如果他按照给定的规则行事,他就可以连续到达每一颗星星。

你的任务是找到驴链可以包含的最大星星数 m 。

请注意,链必须从轴的原点开始,在计算链中星形的数量 m 时不考虑这一点。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 星星的数量。第二行包含表示关系“a/b c/d”的简单分数,例如 $$\frac{a}{b} = \frac{\sin \alpha_{1}}{\cos \alpha_{1}}$$ 和 $$\frac{c}{d} = \frac{\sin\alpha_{2}}{\cos\alpha_{2}}$$ (0 ≤ a, b, c, d ≤ 105; $$0^\circ \leqslant \alpha_1 < \alpha_2 \leqslant 90^\circ$$; $$\frac{a}{b} \neq \frac{0}{0}$$; $$\frac{c}{d} \neq \frac{0}{0}$$)。给定的数字 a、b、c、d 是整数。

接下来的 n 行包含整数对 xi, yi (1 ≤ xi, yi ≤ 105)——星星的坐标。

保证所有星星都有不同的坐标。

输出

在一行中打印数字 m — 问题的答案。

示例

输入 #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

输出 #1

4

注意

在示例中,驴可以构建的最长链由四颗星组成。请注意,驴子无法选择位于他想象的光线上的星星。