P14393 [JOISC 2017] 龙 2 / Dragon 2

在 JOI 平原上，人们与龙共同生活。 JOI 平原是一个具有 $X$ 坐标和 $Y$ 坐标的广阔坐标平面。横坐标为 $x$、纵坐标为 $y$ 的点记作 $(x, y)$。 JOI 平原上有 $N$ 条龙，编号从 $1$ 到 $N$。同时有 $M$ 个龙族部落，编号从 $1$ 到 $M$。龙 $i$（$1 \le i \le N$）始终位于 JOI 平原上的点 $(A_i, B_i)$，其所属部落为 $C_i$。并非所有种类的龙都生活在 JOI 平原上。 在 JOI 平原上，有两个位于点 $(D_1, E_1)$ 和 $(D_2, E_2)$ 的人类村落。两个村落之间由一条道路相连，该道路是连接两村位置的线段。 点 $(A_1, B_1), \dots, (A_N, B_N)$ 与点 $(D_1, E_1), (D_2, E_2)$ 互不相同，且任意三点不共线。 有时，龙族部落之间会发生冲突。若部落 $a$（$1 \le a \le M$）对部落 $b$（$1 \le b \le M, a \ne b$）产生敌意，则部落 $a$ 的每条龙都会向部落 $b$ 的所有龙发射火球。火球沿直线飞向目标，击中目标后仍会沿原方向继续飞行。因此，火球的轨迹是一条半直线。 当部落间发生冲突时，若火球从龙身上经过道路，则道路必须被破坏。你拥有一份未来可能发生的 $Q$ 个龙族部落冲突的清单。对于每个可能的冲突，你需要计算经过道路的火球数量。 **任务** 给定龙、人类村落的信息，以及一份可能发生的龙族部落冲突清单，编写一个程序，对每个冲突计算经过道路的火球数量。

从标准输入读取以下数据： - 第一行包含两个以空格分隔的整数 $N$、$M$。这表示 JOI 平原上有 $N$ 条龙，以及 $M$ 个龙族部落。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含三个以空格分隔的整数 $A_i$、$B_i$、$C_i$。这表示龙 $i$（$1 \le i \le N$）位于 JOI 平原上的点 $(A_i, B_i)$，其所属部落为 $C_i$。 - 下一行包含四个以空格分隔的整数 $D_1$、$E_1$、$D_2$、$E_2$。这表示两个位于 JOI 平原上点 $(D_1, E_1)$ 和 $(D_2, E_2)$ 的人类村落。 - 下一行包含一个整数 $Q$，表示可能发生的龙族部落冲突的数量。 - 接下来的 $Q$ 行中，第 $j$ 行（$1 \le j \le Q$）包含两个以空格分隔的整数 $F_j$、$G_j$。这表示在第 $j$ 个可能的冲突中，部落 $F_j$ 对部落 $G_j$ 产生敌意。

向标准输出写入 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含第 $j$ 个部落冲突中经过道路的火球数量。

### 样例 1 解释 在第一次部落冲突中，满足以下条件： - 龙 1 向龙 3 发射的火球不会经过道路。 - 龙 1 向龙 4 发射的火球不会经过道路。 - 龙 2 向龙 3 发射的火球会经过道路。 - 龙 2 向龙 4 发射的火球不会经过道路。 因此，有 1 个火球经过道路。 在第二次部落冲突中，满足以下条件： - 龙 3 向龙 1 发射的火球会经过道路。 - 龙 3 向龙 2 发射的火球会经过道路。 - 龙 4 向龙 1 发射的火球不会经过道路。 - 龙 4 向龙 2 发射的火球不会经过道路。 因此，有 2 个火球经过道路。 ### 数据范围 所有输入数据满足以下条件： - $2 \le N \le 30000$。 - $2 \le M \le N$。 - $-1000000000 \le A_i \le 1000000000$（$1 \le i \le N$）。 - $-1000000000 \le B_i \le 1000000000$（$1 \le i \le N$）。 - $1 \le C_i \le M$（$1 \le i \le N$）。 - $-1000000000 \le D_1 \le 1000000000$。 - $-1000000000 \le E_1 \le 1000000000$。 - $-1000000000 \le D_2 \le 1000000000$。 - $-1000000000 \le E_2 \le 1000000000$。 - $N + 2$ 个点 $(A_1, B_1), \dots, (A_N, B_N), (D_1, E_1), (D_2, E_2)$ 互不相同，且任意三点不共线。 - $1 \le Q \le 100000$。 - $1 \le F_j \le M$（$1 \le j \le Q$）。 - $1 \le G_j \le M$（$1 \le j \le Q$）。 - $F_j \ne G_j$（$1 \le j \le Q$）。 - $(F_j, G_j) \ne (F_k, G_k)$（$1 \le j < k \le Q$）。 ### 子任务 共有 3 个子任务。每个子任务的得分及额外约束如下： **子任务 1 [15 分]** - $N \le 3000$。 **子任务 2 [45 分]** - $Q \le 100$。 **子任务 3 [40 分]** 无额外约束。 翻译由 Qwen3-235B 完成