LibreOJ

2401 「JOISC 2017 Day 4」Dragon 2

内存限制：256 MB 时间限制：3000 ms

题目描述

题目译自 JOISC 2017 Day4 T3「ドラゴン 2 / Dragon 2」

在一个平面直角坐标系上有 $N$ 条龙，编号为 $1\dots N$；龙有 $M$ 支种族，编号为 $1\ldots M$。
$i$ 号龙 $(1\le i\le N)$ 位于 $(A_i, B_i)$，它属于种族 $C_i$。有可能有些种族已经没有龙了。
JOI 平原上有一条路，这条路可视为一条线段，端点坐标分别为 $(D_1, E_1)$ 和 $(D_2, E_2)$。
上文中提到的所有坐标互不相同，且没有三点共线。
不同种族的龙之间会发生冲突。现给出 $Q$ 种冲突，每种冲突用两个整数 $F_j, G_j$ 来描述 $(1\le j\le Q, 1\le F_j, G_j\le M)$，意为种族 $F_j$ 敌视种族 $G_j$。此时，种族 $F_j$ 的每一条龙会向种族 $G_j$ 的每一条龙发射一个火球。火球轨迹是一条射线，打到对方的龙身上后，火球会穿过龙，沿着刚才的方向继续飞行。保证此后种族 $F_j$ 不会再次敌视种族 $G_j$。
火球会烧坏道路。对于给出的 $Q$ 种冲突，求其中有多少个火球会烧坏道路。

输入格式

第一行有两个整数 $N, M$ ，用空格分隔。
在接下来的 $N$ 行中，第 $i$ 行 $(1\le i\le N)$ 有三个整数 $A_i, B_i, C_i$ 。
第 $N + 2$ 行有四个整数 $D_1, E_1, D_2, E_2$ ，用空格分隔。
第 $N + 3$ 行有一个整数 $Q$ 。
在接下来的 $Q$ 行中，第 $j$ 行 $(1\le i\le Q)$ 有两个用空格分隔的整数 $F_j, G_j$ 。

输出格式

输出共 $Q$ 行，每行一个整数，表示在第 $j$ 种冲突之中，有多少个火球会烧坏道路。

样例 1

在第一种冲突中： * 2 号龙向 3 号龙发射的火球会烧坏道路。 * 1 号龙向 3 号龙、1 号龙向 4 号龙、2 号龙向 4 号龙发射的火球不会烧坏道路。

在第二种冲突中： * 3 号龙向 1 号龙、3 号龙向 2 号龙发射的火球会烧坏道路。 * 4 号龙向 1 号龙、4 号龙向 2 号龙发射的火球不会烧坏道路。

样例 2

样例 3

数据范围与提示

对于 $15\%$ 的数据，$N\le 3000$。
对于另外 $45\%$ 的数据，$Q\le 100$。
对于所有数据，$2\le M\le N\le 3\times 10^4, 1\le Q\le 10^5$ ，所有点的横坐标绝对值、纵坐标绝对值均 $\le 10^9$ ，所有点互不相同，没有三点共线，

样例

样例输入 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