13671367 SUSTech Online Judge
Problem 1367 --[Hard] Intersection of lines

## 1367: [Hard] Intersection of lines

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

## Description

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.

## Input

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.

## Output

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

2
1 3
1 0
-1 3

## Sample Output

YES

[Submit][Status]