CF2002C.Black Circles

普及-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

在一个二维平面上有 nn 个圆。第 ii 个圆的圆心位于 (xi,yi)(x_i, y_i)。最初,所有圆的半径都是 00。

这些圆的半径以每秒 11 单位的速度增长。

你现在的位置是 (xs,ys)(x_s, y_s),你的目标是到达 (xt,yt)(x_t, y_t),并且在这个运动过程中不能碰到任何一个圆的边缘(包括你到达 (xt,yt)(x_t, y_t) 的那一刻)。你可以向任意方向移动。然而,你的速度被限制在每秒 11 单位。

请判断是否有可能实现这一目标。

输入格式

每个测试样例包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。接着是各个测试用例的描述。

每个测试用例的第一行包含一个整数 nn(1≤n≤1051 \le n \le 10^5)——圆的数量。

接下来的 nn 行,每行包含两个整数 xix_i 和 yiy_i(1≤xi,yi≤1091 \le x_i, y_i \le 10^9)——每个圆的圆心坐标。

最后一行包含四个整数 xsx_s,ysy_s,xtx_t,yty_t(1≤xs,ys,xt,yt≤1091 \le x_s, y_s, x_t, y_t \le 10^9)——起点和终点的坐标。

题目保证这 n+2n+2 个点是互不相同的。

题目还保证所有测试用例中 nn 的总和不超过 10510^5。

输出格式

对于每一个测试用例,如果能够不接触任何圆的边缘就能到达目标,则输出 YES\texttt{YES},否则输出 NO\texttt{NO}。

你可以不区分大小写输出 YES\texttt{YES} 和 NO\texttt{NO}(例如,yEs\texttt{yEs}、yes\texttt{yes}、Yes\texttt{Yes} 和 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

说明/提示

在第一个测试用例中,一种可行的移动方式如下图所示。

输入解题思路,AI测评打分。不知道怎么写?

首页