問題一覧 > 通常問題

No.2885 Range Triangle Collision Decision Queries

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 15
作問者 : Iroha_3856 / テスター : Rac tikuwa_ hiro1729
お気に入りにしたユーザー ProblemId : 11068 / 自分の提出
問題文最終更新日: 2024-09-08 14:05:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 445 (菁々祭プログラミングコンテスト2024) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。