来源：ICPC 2023–2024 Northwestern Russia Regional Contest（St Petersburg，2023-11-05）

H. H 形图案（）

• 时间限制： 2 秒
• 内存限制： 1024 MB
• 难度估计： CF 2700

题目描述

若平面上的三个线段 $PQ$、$a$ 和 $b$ 满足以下条件，则称它们构成一个 H 形图案：

1. 点 $P$ 严格位于线段 $a$ 的内部，并且线段 $PQ$ 与 $a$ 不共线；
2. 点 $Q$ 严格位于线段 $b$ 的内部，并且线段 $PQ$ 与 $b$ 不共线；
3. 线段 $a$ 与 $b$ 没有公共点。

合法与非法的 H 形图案

给定点 $P$ 和 $Q$ 的坐标，以及 $n$ 条候选线段。你需要从候选线段中选择一条作为 $a$，再选择另一条作为 $b$，使其与给定线段 $PQ$ 构成 H 形图案。

某些候选线段可能完全重合，但它们仍应被视为不同的线段。

求合法选择方案数。

输入格式

每个输入包含多组测试数据。

第一行包含测试数据组数 $t$（$1\le t\le 10^5$）。

对于每组测试数据：

• 第一行包含四个整数 $x_P,y_P,x_Q,y_Q$，表示点 $P$ 和 $Q$ 的坐标（$-10^9\le x_P,y_P,x_Q,y_Q\le 10^9$）。保证 $P$ 与 $Q$ 不重合；
• 第二行包含一个整数 $n$，表示候选线段数量（$2\le n\le 2\cdot 10^5$）；
• 接下来 $n$ 行，第 $i$ 行包含四个整数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$，表示第 $i$ 条线段两个端点的坐标（所有坐标绝对值不超过 $10^9$）。保证所有线段长度均为正。

保证所有测试数据中 $n$ 的总和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出使用给定线段 $PQ$ 和两条候选线段构成 H 形图案的方案数。

样例

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

6