593B.md (2459B)
1 Source: https://codeforces.com/problemset/problem/593/B 2 3 B. Anton and Lines 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 * *y*' = *k**i* * *x*' + *b**i*, that is, point (*x*', *y*') belongs to the line number *i*; 24 * *y*' = *k**j* * *x*' + *b**j*, that is, point (*x*', *y*') belongs to the line number *j*; 25 * *x*1 < *x*' < *x*2, that is, point (*x*', *y*') lies inside the strip bounded by *x*1 < *x*2. 26 27 You can't leave Anton in trouble, can you? Write a program that solves the given task. 28 29 Input 30 31 The first line of the input contains an integer *n* (2 ≤ *n* ≤ 100 000) — the number of lines in the task given to Anton. The second line contains integers *x*1 and *x*2 ( - 1 000 000 ≤ *x*1 < *x*2 ≤ 1 000 000) defining the strip inside which you need to find a point of intersection of at least two lines. 32 33 The following *n* lines contain integers *k**i*, *b**i* ( - 1 000 000 ≤ *k**i*, *b**i* ≤ 1 000 000) — 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*. 34 35 Output 36 37 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). 38 39 Examples 40 41 Input 42 43 ``` 44 4 45 1 2 46 1 2 47 1 0 48 0 1 49 0 2 50 ``` 51 52 Output 53 54 ``` 55 NO 56 ``` 57 58 Input 59 60 ``` 61 2 62 1 3 63 1 0 64 -1 3 65 ``` 66 67 Output 68 69 ``` 70 YES 71 ``` 72 73 Input 74 75 ``` 76 2 77 1 3 78 1 0 79 0 2 80 ``` 81 82 Output 83 84 ``` 85 YES 86 ``` 87 88 Input 89 90 ``` 91 2 92 1 3 93 1 0 94 0 3 95 ``` 96 97 Output 98 99 ``` 100 NO 101 ``` 102 103 Note 104 105 In the first sample there are intersections located on the border of the strip, but there are no intersections located strictly inside it. 106 107 