codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/484ae6cdaabe3e64ee7305a966c1c2f377da1b57.png)