← 返回题目列表

Codeforces · 2002/C

C. 黑眼圈

中文机器翻译题面 查看原题

二维平面上有 $$$n$$$ 个圆。第 $$$i$$$ 个圆的中心位于 $$$(x_i,y_i)$$$。最初,所有圆的半径均为 $$$0$$$。

圆的半径以每秒 $$$1$$$ 单位的速度增加。

您目前的位置为$$$(x_s,y_s)$$$;您的目标是在不触及任何圆的圆周的情况下到达 $$$(x_t,y_t)$$$(包括到达 $$$(x_t,y_t)$$$ 的那一刻)。您可以朝任何您想要的方向移动。但是,您的速度限制为每秒 $$$1$$$ 单位。

请确定这是否可行。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le10^5$$$) - 圆的数量。

接下来的 $$$n$$$ 行每行包含两个整数 $$$x_i$$$、$$$y_i$$$ ($$$1\le x_i,y_i\le10^9$$$) — 每个圆的中心。

最后一行包含四个整数 $$$x_s$$$, $$$y_s$$$, $$$x_t$$$, $$$y_t$$$ ($$$1\le x_s,y_s,x_t,y_t\le10^9$$$) – 分别是起点和目标的坐标。

保证这些 $$$n+2$$$ 点是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果可以在不接触圆边界的情况下达到目标,则输出 $$$\texttt{YES}$$$,否则输出 $$$\texttt{NO}$$$。

您可以在任何情况下输出 $$$\texttt{Yes}$$$ 和 $$$\texttt{No}$$$(例如,字符串 $$$\texttt{yEs}$$$、$$$\texttt{yes}$$$、$$$\texttt{Yes}$$$ 和 $$$\texttt{YES}$$$ 将被识别为肯定响应)。

示例

输入 #1

7
3
2 5
2 14
10 13
4 9 9 7
3
10 11
6 9
12 12
14 13 4 8
1
5 7
12 6 11 13
2
1000000000 2
2 1000000000
1 1 2 2
1
999999998 1000000000
999999999 999999999 1 1
1
1000000000 1
1 1000000000 1 1
10
989237121 2397081
206669655 527238537
522705783 380636165
532545346 320061691
207818728 199485303
884520552 315781807
992311437 802563521
205138355 324818663
223575704 395073023
281560523 236279118
216941610 572010615 323956540 794523071

输出 #1

YES
NO
YES
YES
YES
NO
YES

注意

第一个测试用例中,可行的移动方式如下。