CF593B.Anton and Lines

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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 nn lines defined by the equations y=kix+biy=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,yx',y' , such that:

  • y=kix+biy'=k_{i}*x'+b_{i} , that is, point (x,y)(x',y') belongs to the line number ii ;
  • y=kjx+bjy'=k_{j}*x'+b_{j} , that is, point (x,y)(x',y') belongs to the line number jj ;
  • x_{1}<x'<x_{2} , that is, point (x,y)(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 nn ( 2<=n<=1000002<=n<=100000 ) — the number of lines in the task given to Anton. The second line contains integers x1x_{1} and x2x_{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 nn lines contain integers kik_{i} , bib_{i} ( 1000000<=ki,bi<=1000000-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 iji≠j it is true that either kikjk_{i}≠k_{j} , or bibjb_{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.

首页