| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 2 | 2 | 2 | 100.000% |
You are given $n$ distinct marked points on a 2D plane, numbered from 1ドル$ to $n$. Marked point $i$ has coordinates $(x_i , y_i)$.
In this problem, you are given $q$ scenarios, numbered from 1ドル$ to $q$. In each scenario $k,ドル four integers $a_k,ドル $b_k,ドル $c_k,ドル and $d_k$ are given, indicating that you initially stand at $(a_k, b_k)$ and aim to reach $(c_k, d_k)$ 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
$\overrightarrow{PT}=\overrightarrow{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.
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 $x_i$ and $y_i$ (0ドル ≤ x_i , y_i ≤ 10^9$). 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 $a_k,ドル $b_k,ドル $c_k,ドル and $d_k$ (0ドル ≤ a_k, b_k, c_k, d_k ≤ 10^9$; $(a_k, b_k) \ne (c_k, d_k)$).
Output $q$ lines. The $k$-th line should contain yes if the objective of scenario $k$ is achievable, or no otherwise.
2 4 10 0 0 10 3 4 6 5 4 0 7 0 4 0 16 0 123 456 789 0
yes yes yes no
There are two marked points $(10, 0)$ and $(0, 10)$. In scenario 1ドル,ドル starting from the point $S = (a_1, b_1) = (3, 4),ドル the objective is achieved as follows:
In scenario 2ドル,ドル you start from $S = (a_2, b_2) = (4, 0)$. Choose $(10, 0)$ as both $P$ and $Q$. A point $T$ is determined with coordinates $(16, 0)$. The point $(c_2, d_2) = (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 $(c_4, d_4) = (789, 0)$ from $(a_4, b_4) = (123, 456)$ is impossible.
Figure M.1: Illustrations of the scenarios in Sample Input #1.