P3483 [POI 2009] STR-Fire Brigade

在 Byteotia 的首都 Bytau，街道布局非常规则。每条街道要么从北到南，要么从东到西。因此，每一条南北街道与每一条东西街道正好在一个点相交。此外，沿着每条街道，其连续的交叉口之间的距离正好是 1 公里。 Bytau 不仅是首都，也是 Byteotia 最古老的城市之一。难怪这里有许多历史建筑，每个都位于一个交叉口。市议会非常重视它们的保护，现在担心火灾的风险。因此，他们决定在城市中建立两个主要的消防站。每个纪念碑将由最近的消防站保护；如果两个消防站距离相等，则由两个消防站共同保护。 Bytau 的住房非常密集，因此欧几里得距离不是首选的度量标准。纪念碑与消防站之间的距离应定义为沿街道之间的最短路径的长度。 市议会已经准备了几个消防站位置的方案。现在要求你确定，对于每个方案，分别有多少纪念碑仅由第一个消防站保护，仅由第二个消防站保护，以及由两个消防站共同保护。

标准输入的第一行有四个整数 $n$、$m$、$z$ 和 $p$ ($1 \le n,m \le 1{,}000{,}000{,}000$, $1 \le z,p \le 100{,}000$)，用单个空格分隔，分别表示：从北到南的街道数量，从东到西的街道数量，Bytau 中的历史建筑数量，以及市议会提出的项目数量。 南北街道从 $1$ 到 $n$ 编号，从西到东。东西街道从 $1$ 到 $m$ 编号，从北到南。第 $x$ 条南北街道和第 $y$ 条东西街道的交叉点将用坐标 $(x,y)$ 表示。 在接下来的 $z$ 行中，每行有两个整数 $x_i$ 和 $y_i$ ($1 \le x_i \le n$, $1 \le y_i \le m$)，用单个空格分隔，表示第 $i$ 个纪念碑的坐标。没有两个不同的纪念碑位于同一个交叉口。 接下来的 $p$ 行中的每一行包含市议会的一个提案 - 四个整数 $x_{j,1}, y_{j,1}, x_{j,2}, y_{j,2}$，用单个空格分隔，$1 \le x_{j,1},x_{j,2} \le n$, $1 \le y_{j,1},y_{j,2} \le m$, $(x_{j,1},y_{j,1}) eq (x_{j,2},y_{j,2})$。坐标 $(x_{j,1},y_{j,1})$ 和 $(x_{j,2},y_{j,2})$ 描述了根据第 $j$ 个提案消防站要设置的位置 $(1 \le j \le p)$。

你的程序应在标准输出中打印出正好 $p$ 行。 在第 $j$ 行中应该有三个整数，分别表示： 仅由市议会第 $j$ 个提案的第一个消防站保护的纪念碑数量，仅由第二个消防站保护的纪念碑数量，以及由两个消防站共同保护的纪念碑数量。 这些数字应以单个空格分隔。

题面翻译由 ChatGPT-4o 提供。