2002C.md (2440B)
1 Source: https://codeforces.com/problemset/problem/2002/C 2 3 C. Black Circles 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 There are $n$ circles on a two-dimensional plane. The $i$-th circle is centered at $(x_i,y_i)$. Initially, all circles have a radius of $0$. 22 23 The circles' radii increase at a rate of $1$ unit per second. 24 25 You are currently at $(x_s,y_s)$; your goal is to reach $(x_t,y_t)$ without touching the circumference of any circle (including the moment you reach $(x_t,y_t)$). You can move in any direction you want. However, your speed is limited to $1$ unit per second. 26 27 Please determine whether this is possible. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le10^4$). The description of the test cases follows. 32 33 The first line of each test case contains a single integer $n$ ($1\le n\le10^5$) — the number of circles. 34 35 The next $n$ lines each contain two integers $x_i$, $y_i$ ($1\le x_i,y_i\le10^9$) — the center of each circle. 36 37 The final line contains four integers $x_s$, $y_s$, $x_t$, $y_t$ ($1\le x_s,y_s,x_t,y_t\le10^9$) — the coordinates of the starting point and the goal, respectively. 38 39 It is guaranteed that these $n+2$ points are distinct. 40 41 It is guaranteed that the sum of $n$ over all testcases does not exceed $10^5$. 42 43 Output 44 45 For each test case, output $\texttt{YES}$ if it is possible to reach the goal without touching the circle boundaries, and output $\texttt{NO}$ otherwise. 46 47 You can output $\texttt{Yes}$ and $\texttt{No}$ in any case (for example, strings $\texttt{yEs}$, $\texttt{yes}$, $\texttt{Yes}$, and $\texttt{YES}$ will be recognized as a positive response). 48 49 Example 50 51 Input 52 53 ``` 54 7 55 56 3 57 58 2 5 59 60 2 14 61 62 10 13 63 64 4 9 9 7 65 66 3 67 68 10 11 69 70 6 9 71 72 12 12 73 74 14 13 4 8 75 76 1 77 78 5 7 79 80 12 6 11 13 81 82 2 83 84 1000000000 2 85 86 2 1000000000 87 88 1 1 2 2 89 90 1 91 92 999999998 1000000000 93 94 999999999 999999999 1 1 95 96 1 97 98 1000000000 1 99 100 1 1000000000 1 1 101 102 10 103 104 989237121 2397081 105 106 206669655 527238537 107 108 522705783 380636165 109 110 532545346 320061691 111 112 207818728 199485303 113 114 884520552 315781807 115 116 992311437 802563521 117 118 205138355 324818663 119 120 223575704 395073023 121 122 281560523 236279118 123 124 216941610 572010615 323956540 794523071 125 ``` 126 127 Output 128 129 ``` 130 YES 131 NO 132 YES 133 YES 134 YES 135 NO 136 YES 137 ``` 138 139 Note 140 141 In the first test case, a feasible way of movement is as follows. 142 143 