P17126 [ICPC 2025 Shanghai R] Flower' s land 4

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

在二维平面上有 $n$ 条线段。每条线段均以 **$x$ 轴的非负半轴** 上的一点为起点，以 **$y$ 轴的非负半轴** 上的一点为终点。换言之，其起点坐标为 $(x_i, 0)$，其中 $x_i \ge 0$，终点坐标为 $(0, y_i)$，其中 $y_i \ge 0$。 你需要回答 $q$ 个查询。每个查询会给出另一条线段，该线段起点在 $x$ 轴上，终点可以在平面的 **第一象限或坐标轴的非负部分** 上的任意位置。对于每条查询线段，请判断它是否与任何已有线段相交。**端点处的相交也算作相交。** 查询之间相互独立；也就是说，每次查询给出的线段不会保留到后续的查询中。

输入包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试用例的数量。 对于每组测试用例，第一行包含两个整数 $n, q$ ($1 \le n, q \le 10^6$)，分别表示已有线段的数量和查询的数量。 接下来 $n$ 行，每行包含两个整数 $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$)，描述一条以 $(x_i, 0)$ 为起点、以 $(0, y_i)$ 为终点的线段。 再接下来 $q$ 行，每行包含三个整数 $a_j, b_j, c_j$ ($0 \le a_j, b_j, c_j \le 10^9$)，描述一条查询线段，其起点为 $(a_j, 0)$，终点为 $(b_j, c_j)$。 保证所有测试用例的 $n$ 之和与 $q$ 之和分别不超过 $10^6$。

对于每个查询，如果该查询线段与至少一条已有线段相交（包括端点处），则输出 `YES`，否则输出 `NO`。

翻译由 DeepSeek V4 Pro 完成