No.2885 Range Triangle Collision Decision Queries
タグ : / 解いたユーザー数 15
作問者 :
Iroha_3856
/ テスター :
Problem Statement
There are $N$ triangles on the $xy$-plane, named $T_1, T_2, \ldots, T_N$.
For $i = 1, 2, \ldots, N$, the coordinates of the three vertices of $T_i$ are $(A_i, B_i), (A_i-D_i, B_i-D_i), (A_i+D_i, B_i-D_i)$.
For $i = 1, 2, \ldots, Q$, answer the following query.
- Given $S_i, L_i, R_i$, determine whether $T_{S_i}$ has an intersection of positive area with all of $T_{L_i}, T_{L_i+1}, \ldots, T_{R_i}$ (note that touching is not considered positive).
Here, $T_i$ and $T_i$ are considered to have a positive intersection.
Input
$N$ $A_1\ B_1\ D_1$ $A_2\ B_2\ D_2$ $\vdots$ $A_N\ B_N\ D_N$ $Q$ $S_1\ L_1\ R_1$ $S_2\ L_2\ R_2$ $\vdots$ $S_Q\ L_Q\ R_Q$
All input satisfies the following constraints.
- $1 \leq N \leq 2 \times 10^{5}$
- $-10^{16} \leq A_i, B_i \leq 10^{16}$
- $1 \leq D_i \leq 10^{16}$
- $1 \leq Q \leq 2 \times 10^5$
- $1 \leq S_i \leq N$
- $1 \leq L_i \leq R_i \leq N$
- All input values are integers.
Output
Output $Q$ lines.
On the $i$-th line, output Yes if $T_{S_i}$ has a positive intersection with all of $T_{L_i}, T_{L_i+1}, \ldots, T_{R_i}$, and No otherwise, followed by a newline.
Also output a newline after the $Q$-th line.
Sample
Sample 1
Input
4 5 5 4 2 5 3 5 6 2 -2 6 2 3 1 1 3 3 1 2 4 1 3
Output
Yes No No
The triangles are drawn as follows.
- For the $1$-st query, $T_1$ has a positive intersection with all of $T_1, T_2, T_3$, so output
Yes. - For the $2$-nd query, $T_3$ has a positive intersection with $T_1$, but it only touches $T_2$ and has no positive intersection with it, so output
No. - For the $3$-rd query, $T_4$ has no positive intersection with any of $T_1, T_2, T_3$, so output
No.
Sample 2
Input
1 10000000000000000 10000000000000000 10000000000000000 1 1 1 1
Output
Yes
The input values may not fit in a 32-bit integer.
Also, $N = 1$ is possible.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。