codeforces-scrape

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

2119B.md (2979B)


      1 Source: https://codeforces.com/problemset/problem/2119/B
      2 
      3 B. Line Segments
      4 
      5 time limit per test
      6 
      7 1.5 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 [PIKASONIC - Lost My Mind (feat.nakotanmaru)](https://www.youtube.com/watch?v=iprl3wJnWoo)
     22 
     23 You are given two points $(p_x,p_y)$ and $(q_x,q_y)$ on a Euclidean plane.
     24 
     25 You start at the starting point $(p_x,p_y)$ and will perform $n$ operations. In the $i$-th operation, you must choose any point such that the Euclidean distance$^{\text{∗}}$ between your current position and the point is exactly $a_i$, and then move to that point.
     26 
     27 Determine whether it is possible to reach the terminal point $(q_x,q_y)$ after performing all operations.
     28 
     29 $^{\text{∗}}$The Euclidean distance between $(x_1, y_1)$ and $(x_2, y_2)$ is $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
     30 
     31 Input
     32 
     33 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.
     34 
     35 The first line of each test case contains a single integer $n$ ($1\leq n \leq 10^3$) — the length of the sequence $a$.
     36 
     37 The second line of each test case contains four integers $p_x,p_y,q_x,q_y$ ($1\leq p_x,p_y,q_x,q_y\leq 10^7$) — the coordinates of the starting point and terminal point.
     38 
     39 The third line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^4$) — the distance to move in each operation.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output "Yes" if it is possible to reach the terminal point $(q_x,q_y)$ after all operations; otherwise, output "No".
     46 
     47 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.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 5
     55 
     56 2
     57 
     58 1 1 5 1
     59 
     60 3 3
     61 
     62 3
     63 
     64 1 1 3 3
     65 
     66 2 3 4
     67 
     68 2
     69 
     70 100 100 100 100
     71 
     72 4 5
     73 
     74 1
     75 
     76 5 1 1 4
     77 
     78 5
     79 
     80 2
     81 
     82 10000000 10000000 10000000 10000000
     83 
     84 10000 10000
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 Yes
     91 Yes
     92 No
     93 Yes
     94 Yes
     95 ```
     96 
     97 Note
     98 
     99 Here is a picture that shows a possible movement of the first test case. The coordinates of point $r_1$ are $(3,1+\sqrt{5})$.
    100 
    101  ![](https://espresso.codeforces.com/4bb380de077bba6d4efe150c19f8ecefdf92f011.png) The first test case. 
    102 
    103 Here is a picture that shows a possible movement of the second test case. The coordinates of point $r_1$ are $(1+\sqrt{3},0)$, and the coordinates of point $r_2$ are $\left(-\frac{(\sqrt{3}+4)(3\sqrt{3(149-24\sqrt{3})}-7\sqrt{3}-38)}{104},-\frac{\sqrt{3(1331-764\sqrt{3})}+12\sqrt{3}-27}{104}\right)$.
    104 
    105  ![](https://espresso.codeforces.com/6616aa240a030d50075aca3ca14cf54501d4f21d.png) The second test case. 
    106 
    107 For the third test case, it can be shown that there is no set of moves that satisfies all requirements.
    108 
    109 Here is a picture that shows a possible movement of the fourth test case.
    110 
    111  ![](https://espresso.codeforces.com/db54fedff28db688eddb8b1f7d23c4f549dfbe25.png) The fourth test case.