codeforces-scrape

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

1805C.md (3228B)


      1 Source: https://codeforces.com/problemset/problem/1805/C
      2 
      3 C. Place for a Selfie
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 universe is a coordinate plane. There are $n$ space highways, each of which is a straight line $y=kx$ passing through the origin $(0, 0)$. Also, there are $m$ asteroid belts on the plane, which we represent as open upwards parabolas, i. e. graphs of functions $y=ax^2+bx+c$, where $a \gt 0$.
     22 
     23 You want to photograph each parabola. To do this, for each parabola you need to choose a line that does not intersect this parabola and does not touch it. You can select the same line for different parabolas. Please find such a line for each parabola, or determine that there is no such line.
     24 
     25 Input
     26 
     27 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     28 
     29 The first line of each test case contains $2$ integers $n$ and $m$ ($1 \le n, m \le 10^5$) —the number of lines and parabolas, respectively.
     30 
     31 Each of the next $n$ lines contains one integer $k$ ($|k| \le 10^8$), denoting a line that is described with the equation $y=kx$. The lines are not necessarily distinct, $k$ can be equal to $0$.
     32 
     33 Each of the next $m$ lines contains $3$ integers $a$, $b$, and $c$ ($a, |b|, |c| \le 10^8$, $a \gt 0$) — coefficients of equations of the parabolas $ax^2+bx+c$. The parabolas are not necessarily distinct.
     34 
     35 It is guaranteed that the sum $n$ over all test cases does not exceed $10^5$, and the sum $m$ over all test cases also does not exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case, output the answers for each parabola in the given order. If there is a line that does not intersect the given parabola and doesn't touch it, print on a separate line the word "YES", and then on a separate line the number $k$ — the coefficient of this line. If there are several answers, print any of them. If the line does not exist, print one word "NO".
     40 
     41 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     42 
     43 The empty lines in the output in the example are given only for illustration, you do not need to output them (but you can).
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 1 2
     53 
     54 1
     55 
     56 1 -1 2
     57 
     58 1 -1 3
     59 
     60 2 2
     61 
     62 1
     63 
     64 4
     65 
     66 1 2 1
     67 
     68 2 5 1
     69 
     70 1 1
     71 
     72 0
     73 
     74 1 0 0
     75 
     76 1 1
     77 
     78 100000000
     79 
     80 100000000 100000000 100000000
     81 
     82 2 3
     83 
     84 0
     85 
     86 2
     87 
     88 2 2 1
     89 
     90 1 -2 1
     91 
     92 1 -2 -1
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 YES
     99 1
    100 YES
    101 1
    102 
    103 YES
    104 1
    105 YES
    106 4
    107 
    108 NO
    109 
    110 YES
    111 100000000
    112 
    113 YES
    114 0
    115 NO
    116 NO
    117 ```
    118 
    119 Note
    120 
    121 In the first test case, both parabolas do not intersect the only given line $y=1\cdot x$, so the answer is two numbers $1$.
    122 
    123  ![](https://espresso.codeforces.com/40783cd5ddbf7f169a0a305854310b9217eb6bee.png) 
    124 
    125 In the second test case, the line $y=x$ and the parabola $2x^2+5x+1$ intersect, and also the line $y=4x$ and the parabola $x^2+2x+1$ touch, so these pairs do not satisfy the condition. So for the first parabola, the answer is $1$ ($y=1x$), and for the second parabola — $4$.
    126 
    127  ![](https://espresso.codeforces.com/ce60a048135c3a4e5a945d3f624f3f27c218bc86.png) 
    128 
    129 In the third test set, the line and the parabola intersect, so the answer is "NO".