← 返回题目列表

Codeforces · 593/B

B. 安东和线条

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

老师给了 Anton 一份很大的几何作业,但他没有做(像往常一样),因为他参加了 Codeforces 的常规回合。在任务中,他得到了一组由方程 y = ki·x + bi 定义的 n 条线。有必要确定其中两条线是否至少有一个交点,该交点严格位于 x1 < x2 之间的带内。换句话说,是否存在 1 ≤ i < j ≤ n 和 x', y',使得:

- y' = ki * x' + bi,即点(x', y')属于第i行;
- y' = kj * x' + bj,即点(x', y')属于第j行;
- x1 < x' < x2,即点 (x', y') 位于以 x1 < x2 为界的带内。

你不能让安东陷入麻烦,不是吗?编写一个程序来解决给定的任务。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 100 000) — 分配给 Anton 的任务的行数。第二行包含整数 x1 和 x2 (- 1 000 000 ≤ x1 < x2 ≤ 1 000 000),定义您需要在其中找到至少两条线的交点的条带。

以下 n 行包含整数 ki, bi ( - 1 000 000 ≤ ki, bi ≤ 1 000 000) - 行的描述。保证所有线都是成对不同的,也就是说,对于任意两个 i ≠ j ,要么 ki ≠ kj,要么 bi ≠ bj。

输出

如果两条不同的线至少有一个交点,并且严格位于条带内部,则打印“是”(不带引号)。否则打印“No”(不带引号)。

示例

输入 #1

4
1 2
1 2
1 0
0 1
0 2

输出 #1

NO

输入 #2

2
1 3
1 0
-1 3

输出 #2

YES

输入 #3

2
1 3
1 0
0 2

输出 #3

YES

输入#4

2
1 3
1 0
0 3

输出#4

NO

注意

在第一个示例中,带的边界上有交叉点,但严格内部没有交叉点。