← 返回题目列表

Codeforces · 2073/M

M. 你能到达那里吗?

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

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Can You Reach There? - 原题 PDF 第 1 页
原题PDF第25页
Can You Reach There? - 原题 PDF 第 2 页
原题PDF第26页
可复制的 PDF 提取文本
Problem M
              Can You Reach There?
                     Time limit: 2 seconds


You are given n distinct marked points on a 2D plane, numbered from 1 to n. Marked point i has coordinates (xi, yi).

In this problem, you are given q scenarios, numbered from 1 to q. In each scenario k, four integers ak, bk, ck, and
dk are given, indicating that you initially stand at (ak, bk) and aim to reach (ck, dk) by repeating the steps described
below any number of times.

In a single step, you choose two marked points P and Q, which may be identical. Let S denote the point where you
are currently standing, and define a point T by
                            −→  −→
                               PT = SQ.

In other words, T is chosen so that the vector from P to T has the same direction and length as the vector from S to
Q. You may then move to any point on the segment ST, including the point T itself, and you will stand at that new
point.

For each scenario, determine whether the objective can be achieved using the described steps. Note that all scenarios
are independent of each other.

Input

The first line of input contains two integers n and q (1 ≤n ≤100 000, 1 ≤q ≤100 000). The i-th of the next n lines
contains two integers xi and yi (0 ≤xi, yi ≤109). The input guarantees that no two marked points have the same
coordinates.

The next q lines represent the scenarios. The k-th of these lines contains four integers ak, bk, ck, and dk (0 ≤
ak, bk, ck, dk ≤109; (ak, bk) ̸= (ck, dk)).

Output

Output q lines. The k-th line should contain yes if the objective of scenario k is achievable, or no otherwise.

 Sample Input #1                          Sample Output #1

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


Explanation for the sample input/output #1

There are two marked points (10, 0) and (0, 10). In scenario 1, starting from the point S = (a1, b1) = (3, 4), the
objective is achieved as follows:

     • In the first step, choose (10, 0) as P and (0, 10) as Q. A point T is determined with coordinates (7, 6). Move to
      a point (40/7, 75/14), which lies on the segment ST. (Figure M.1 (a))


The 2025 ICPC Asia Pacific Championship Problem M: Can You Reach There?

• In the next step, choose (10, 0) as both P and Q. A point T is determined with coordinates (100/7, −75/14).
     From there, you can reach the point (c1, d1) = (6, 5). (Figure M.1 (b))


In scenario 2, you start from S = (a2, b2) = (4, 0). Choose (10, 0) as both P and Q. A point T is determined with
coordinates (16, 0). The point (c2, d2) = (7, 0) is on the segment ST, allowing you to reach there in a single step.
(Figure M.1 (c))

In scenario 3, the objective is similarly achievable.

In scenario 4, it can be shown that reaching the point (c4, d4) = (789, 0) from (a4, b4) = (123, 456) is impossible.


                                                                                        16   10                                        10
                                                                                        14
    8                                         8                                                                                        12
                    T                                                          10    6                                         6             S
                                                                    (c1, d1)            8
    4                                         4
        S = (a1, b1)                                                                6
                                                                                         4    2                                         2
                                                                                         2
    0                                         0                                   S (c2, d2)         T                                                                                         0
        0     2     4     6     8    10            0     2     4     6     8    10           0   2   4   6   8  10  12  14  16

                    (a)                                     (b)                                       (c)


                          Figure M.1: Illustrations of the scenarios in Sample Input #1.





The 2025 ICPC Asia Pacific Championship Problem M: Can You Reach There?