asm_second 题解(坐标转换+二维偏序)

发布时间 2023-05-02 13:46:15作者: victoryang

Question

Asm.Def 在第一象限内找到了n个可疑点。他需要为导弹规划路径。

image

如图所示,导弹一开始在(0,0)。它只能朝着一定的方向——即严格夹在图中两条射线间的方向(白色部分)前进。注意,它不能沿着这两条射线前进,当然也不能停在原地。

image

当导弹到达某个可疑点后,它仍然只能朝着该范围内的方向前进,如上图。

求导弹最多能经过多少个可疑点。

输入格式

\(1\) 行包括 \(1\) 个整数 \(n\)
\(2\)\(4\)个整数 \(a,b,c,d\):代表两条射线的斜率分别是 \(\dfrac{a}{b}\)\(\dfrac{c}{d}\)
接下来 \(n\) 行,每行 \(2\) 个整数 \(x_i,y_i\)(1<=xi,yi<=10^5),代表 \(i\) 号可疑点的坐标。

输出格式

一个整数,即最多能经过几个可疑点。

样例解释

image

数据范围

对于 30% 的数据,\(n \leq 1000,a=0,b=1,c=1,d=0\)

对于 60% 的数据,\(n \leq 1000\)

对于 100% 的数据有:

  • \(n \leq 10^5\)

  • \(0 \leq a,b,c,d \leq 10^5\)

  • \(\dfrac{a}{b}<\dfrac{c}{d}\)(即 \(\dfrac{a}{b}\) 为靠下的那条曲线)

  • \(\dfrac{a}{b} \neq \dfrac{0}{0},\dfrac{c}{d} \neq \dfrac{0}{0}\)

  • \(1 \leq x_i,y_i \leq 10^5\)