P16052 [ICPC 2022 NAC] Triangular Logs

当地森林里有很多树！每棵树都位于整数坐标上，并具有整数高度。砍倒任何一棵树都会得到一根长度等于其高度的圆木。你想通过砍倒三棵树来获得三根 三角形圆木（即能构成非退化三角形的三根圆木）。 给定若干询问，每个询问指定一个轴对齐的矩形区域。问能否通过砍伐该区域内的三棵树（包括位于矩形边界上的树）得到三根三角形圆木？

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$），其中 $n$ 是树的数量，$q$ 是询问的数量。 接下来的 $n$ 行，每行包含三个整数 $x$、$y$ 和 $h$（$1 \le x, y, h \le 10^9$），表示一棵位于 $(x, y)$、高度为 $h$ 的树。所有树的位置互不相同。 接下来的 $q$ 行，每行包含四个整数 $x_{\text{low}}$、$y_{\text{low}}$、$x_{\text{high}}$ 和 $y_{\text{high}}$（$1 \le x_{\text{low}} \le x_{\text{high}} \le 10^9$，$1 \le y_{\text{low}} \le y_{\text{high}} \le 10^9$），描述一个询问的轴对齐矩形区域。

输出 $q$ 行，每行包含一个整数，表示对应询问的答案。如果查询区域内存在三棵树能构成非退化三角形，则输出 $1$，否则输出 $0$。按输入顺序输出询问的答案。

翻译由 DeepSeek V3.2 完成