CF44G Shooting Gallery

Berland 游乐园的射击廊被公认为世界上最棒的之一。每天，国内最优秀的射手都在这里磨练射击技巧，许多游客也竞争着打击飞碟以赢得丰厚奖品。而最近，公园负责人决定开发一个在线版的射击廊。在开发过程中，他们发现需要一个能有效模拟射击过程的程序。为明确程序需求，他们对射击廊做了形式化描述。引入了三维笛卡尔坐标系，$X$ 轴沿着射手所在直线，通过射击场地，$Y$ 轴垂直于场地墙面，沿着墙壁的方向，$Z$ 轴的正方向是射击的方向。我们将 $XOY$ 平面称作“射击平面”，假设所有子弹都从这个区域上的某一点发射，并且沿 $Z$ 轴正方向平行飞行。每一个飞碟可以表示为一个矩形，其边平行于 $X$ 和 $Y$ 轴，并且它有一个正的 $z$ 坐标。每个飞碟与射击平面的距离都不相同。只要子弹穿过对应矩形的内部或边界，就算击中了该目标。当击中目标时，目标会垂直下落到射击廊地下，不再能被射击。目标非常坚固，子弹不能完全穿透目标，如果子弹击中某个目标，则不会继续前进。输入中会给出所有目标的位置，以及所有射击的位置和顺序。你的任务是判断每一次射击击中了哪个目标。

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$）——目标的数量。接下来 $n$ 行，每行包含五个整数 $x_{l},x_{r},y_{l},y_{r},z$，描述一个目标在空间中的位置（$0 \leq x_{l} < x_{r} \leq 10^{7}$，$0 \leq y_{l} < y_{r} \leq 10^{7}$，$0 < z \leq 10^{7}$）。下一行包含一个整数 $m$（$1 \leq m \leq 10^{5}$），表示射击数量。接下来 $m$ 行，每行两个整数 $(x, y)$，表示一颗子弹在射击平面上的坐标（$0 \leq x, y \leq 10^{7}$，所有坐标均为整数）。射击按照开枪顺序给出。每两次射击间隔足够大，且目标下落很快，因此被击落的目标不会影响到之后的射击。

对于每一次射击，输出一行，表示本次射击击中的目标编号，如果没有击中任何目标则输出 $0$。目标的编号从 $1$ 起，按照输入顺序依次编号。

由 ChatGPT 5 翻译