Problem F: [Hard] Intersection of lines

Problem F: [Hard] Intersection of lines

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1635  Solved: 274
[Submit][Status][Web Board]


Given a set of lines, in form of y = kix +bi , where ki and bi are all integers. You are asked to judge whether there exists a pair of lines that intersect strictly inside the interval (x1,x2) (x1<x2, x1 and x2 are integers). That is, the intersection point of two distincet lines, p(x,y), needs to satisfy that x1<x<x2.


The first line of the input contains an integer n (2 ≤ n ≤ 105), which shows the number of lines given.

The second line contains two integers x1 and x2 ( - 109 ≤ x1 < x2  ≤ 109) defining the interval that the intersection point should be strictly in.

The following n lines contain integers ki , bi ( - 106 ≤ ki , bi ≤ 106), which describe lines. It is guaranteed that all lines are pairwise distinct.


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

Sample Input

1 3
1 0
-1 3

Sample Output