#214509. [JOISC 2017] 龙 2 / Dragon 2

在 JOI 平原上，人们与龙共同生活。

JOI 平原是一个具有 坐标和 坐标的广阔坐标平面。横坐标为 、纵坐标为 的点记作 。

JOI 平原上有 条龙，编号从 到 。同时有 个龙族部落，编号从 到 。龙 （）始终位于 JOI 平原上的点 ，其所属部落为 。并非所有种类的龙都生活在 JOI 平原上。

在 JOI 平原上，有两个位于点 和 的人类村落。两个村落之间由一条道路相连，该道路是连接两村位置的线段。

点 与点 互不相同，且任意三点不共线。

有时，龙族部落之间会发生冲突。若部落 （）对部落 （）产生敌意，则部落 的每条龙都会向部落 的所有龙发射火球。火球沿直线飞向目标，击中目标后仍会沿原方向继续飞行。因此，火球的轨迹是一条半直线。

当部落间发生冲突时，若火球从龙身上经过道路，则道路必须被破坏。你拥有一份未来可能发生的 个龙族部落冲突的清单。对于每个可能的冲突，你需要计算经过道路的火球数量。

任务

给定龙、人类村落的信息，以及一份可能发生的龙族部落冲突清单，编写一个程序，对每个冲突计算经过道路的火球数量。

从标准输入读取以下数据：

• 第一行包含两个以空格分隔的整数 、。这表示 JOI 平原上有 条龙，以及 个龙族部落。
• 接下来的 行中，第 行（）包含三个以空格分隔的整数 、、。这表示龙 （）位于 JOI 平原上的点 ，其所属部落为 。
• 下一行包含四个以空格分隔的整数 、、、。这表示两个位于 JOI 平原上点 和 的人类村落。
• 下一行包含一个整数 ，表示可能发生的龙族部落冲突的数量。
• 接下来的 行中，第 行（）包含两个以空格分隔的整数 、。这表示在第 个可能的冲突中，部落 对部落 产生敌意。

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

样例输入 1

4 2
0 1 1
0 -1 1
1 2 2
-6 1 2
-2 0 2 0
2
1 2
2 1

样例输出 1

1
2

样例输入 2

3 2
-1000000000 -1 1
-999999998 -1 1
0 0 2
999999997 1 999999999 1
1
1 2

样例输出 2

1

样例输入 3

6 3
2 -1 1
1 0 1
0 3 2
2 4 2
5 4 3
3 9 3
0 0 3 3
6
1 2
1 3
2 1
2 3
3 1
3 2

样例输出 3

4
2
4
0
2
1

样例 1 解释

在第一次部落冲突中，满足以下条件：

• 龙 1 向龙 3 发射的火球不会经过道路。
• 龙 1 向龙 4 发射的火球不会经过道路。
• 龙 2 向龙 3 发射的火球会经过道路。
• 龙 2 向龙 4 发射的火球不会经过道路。

因此，有 1 个火球经过道路。

在第二次部落冲突中，满足以下条件：

• 龙 3 向龙 1 发射的火球会经过道路。
• 龙 3 向龙 2 发射的火球会经过道路。
• 龙 4 向龙 1 发射的火球不会经过道路。
• 龙 4 向龙 2 发射的火球不会经过道路。

因此，有 2 个火球经过道路。

数据范围

所有输入数据满足以下条件：

• 。
• 。
• （）。
• （）。
• （）。
• 。
• 。
• 。
• 。
• 个点 互不相同，且任意三点不共线。
• 。
• （）。
• （）。
• （）。
• （）。

子任务

共有 3 个子任务。每个子任务的得分及额外约束如下：

子任务 1 [15 分]

• 。

子任务 2 [45 分]

• 。

子任务 3 [40 分]

无额外约束。

翻译由 Qwen3-235B 完成