QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

#14338. Can You Reach There?

الإحصائيات

在二维平面上有 $n$ 个不同的标记点,编号从 1 到 $n$。标记点 $i$ 的坐标为 $(x_i, y_i)$。

本题共有 $q$ 个场景,编号从 1 到 $q$。在每个场景 $k$ 中,给定四个整数 $a_k, b_k, c_k$ 和 $d_k$,表示你初始位于 $(a_k, b_k)$,目标是到达 $(c_k, d_k)$。你可以重复执行以下步骤任意多次:

在单次步骤中,选择两个标记点 $P$ 和 $Q$(它们可以相同)。设 $S$ 为你当前所处的位置,定义点 $T$ 满足 $\vec{PT} = \vec{SQ}$。

换句话说,点 $T$ 的选取使得从 $P$ 到 $T$ 的向量与从 $S$ 到 $Q$ 的向量方向相同且长度相等。之后,你可以移动到线段 $ST$ 上的任意一点(包括点 $T$ 本身),并停留在该新位置。

对于每个场景,请判断目标是否可以通过上述步骤实现。注意,所有场景之间相互独立。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 100\,000$, $1 \le q \le 100\,000$)。接下来 $n$ 行,第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 10^9$)。输入保证没有两个标记点的坐标相同。

接下来 $q$ 行表示场景。第 $k$ 行包含四个整数 $a_k, b_k, c_k$ 和 $d_k$ ($0 \le a_k, b_k, c_k, d_k \le 10^9$; $(a_k, b_k) \neq (c_k, d_k)$)。

输出格式

输出 $q$ 行。如果场景 $k$ 的目标可以实现,则第 $k$ 行输出 yes,否则输出 no

样例

输入 1

2 4
10 0
0 10
3 4 6 5
4 0 7 0
4 0 16 0
123 456 789 0

输出 1

yes
yes
yes
no

说明

现有两个标记点 $(10, 0)$ 和 $(0, 10)$。在场景 1 中,从点 $S = (a_1, b_1) = (3, 4)$ 出发,目标达成过程如下:

  • 第一步,选择 $(10, 0)$ 作为 $P$,$(0, 10)$ 作为 $Q$。确定点 $T$ 的坐标为 $(7, 6)$。移动到线段 $ST$ 上的点 $(40/7, 75/14)$。(图 M.1 (a))
  • 下一步,选择 $(10, 0)$ 同时作为 $P$ 和 $Q$。确定点 $T$ 的坐标为 $(100/7, 75/14)$。从该点出发,可以到达目标点 $(c_1, d_1) = (6, 5)$。(图 M.1 (b))

在场景 2 中,从 $S = (a_2, b_2) = (4, 0)$ 出发。选择 $(10, 0)$ 同时作为 $P$ 和 $Q$。确定点 $T$ 的坐标为 $(16, 0)$。点 $(c_2, d_2) = (7, 0)$ 位于线段 $ST$ 上,因此可以在一步内到达。(图 M.1 (c))

在场景 3 中,目标同样可以实现。

在场景 4 中,可以证明从 $(a_4, b_4) = (123, 456)$ 到达点 $(c_4, d_4) = (789, 0)$ 是不可能的。

图 M.1:样例输入 #1 中各场景的示意图。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#729EditorialClosedNew Editorial for Problem #14338fhq_treap2026-01-16 17:56:26View

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.