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}<x_{2} $ . In other words, is it true that there are $ 1<=i<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}<x'<x_{2} $ , that is, point $ (x',y') $ lies inside the strip bounded by $ x_{1}<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}<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.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF593B/e1a49e4b0c04e7481c4ca085ab81f29a92c6744a.png)