Anton and Lines

题意翻译

**【题目描述】** 给定 $n$ 条形如 $y=k_ix+b_i$ 的直线，你需要判断是否存在两条直线 $a,b$，使 $a,b$ 的交点 $(x_0,y_0)$ 满足 $x_1<x_0<x_2$。 **【输入格式】** 第一行三个整数 $n,x_1,x_2$，意义如题述。 接下来 $n$ 行，每行两个整数 $k_i,b_i$，描述每条直线。 **【输出格式】** 如果存在这样的交点，输出 `YES`。否则输出 `NO`。 **【数据规模与约定】** $1\le n\le 10^5$，$-10^6\le x_1,x_2,k_i,b_i\le 10^6$。 数据保证对于每两条直线 $i,j(i\ne j)$，都有 $k_i\ne k_j$ 或 $b_i\ne b_j$。 Translated By [Sept](/user/224931)

题目描述

The teacher gave Anton a large geometry homework, but he didn't do it (as usual) as he participated in a regular round on Codeforces. In the task he was given a set of $ n $ lines defined by the equations $ y=k_{i}·x+b_{i} $ . It was necessary to determine whether there is at least one point of intersection of two of these lines, that lays strictly inside the strip between $ x_{1}&lt;x_{2} $ . In other words, is it true that there are $ 1<=i&lt;j<=n $ and $ x',y' $ , such that: - $ y'=k_{i}*x'+b_{i} $ , that is, point $ (x',y') $ belongs to the line number $ i $ ; - $ y'=k_{j}*x'+b_{j} $ , that is, point $ (x',y') $ belongs to the line number $ j $ ; - $ x_{1}&lt;x'&lt;x_{2} $ , that is, point $ (x',y') $ lies inside the strip bounded by $ x_{1}&lt;x_{2} $ . You can't leave Anton in trouble, can you? Write a program that solves the given task.

输入输出格式

输入格式

The first line of the input contains an integer $ n $ ( $ 2<=n<=100000 $ ) — the number of lines in the task given to Anton. The second line contains integers $ x_{1} $ and $ x_{2} $ ( $ -1000000<=x_{1}&lt;x_{2}<=1000000 $ ) defining the strip inside which you need to find a point of intersection of at least two lines. The following $ n $ lines contain integers $ k_{i} $ , $ b_{i} $ ( $ -1000000<=k_{i},b_{i}<=1000000 $ ) — the descriptions of the lines. It is guaranteed that all lines are pairwise distinct, that is, for any two $ i≠j $ it is true that either $ k_{i}≠k_{j} $ , or $ b_{i}≠b_{j} $ .

输出格式

Print "Yes" (without quotes), if there is at least one intersection of two distinct lines, located strictly inside the strip. Otherwise print "No" (without quotes).

输入输出样例

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

说明

In the first sample there are intersections located on the border of the strip, but there are no intersections located strictly inside it.