P14696 [ICPC 2024 Tehran R] PCB

在设计印刷电路板（PCB）时，每个用电设备必须通过导电导线连接到电源。PCB 是一个宽度为 $W$、高度为 $H$ 的矩形。它被表示为一个从 $(0,0)$ 到 $(W+1,H+1)$ 的整数坐标网格。 电路板左边缘有 $n$ 个电源，板内还有 $n$ 个用电设备。第 $i$ 个电源位于位置 $(0,h_i)$，第 $i$ 个用电设备位于位置 $(x_i,y_i)$。每个电源必须恰好连接到一个用电设备，反之亦然。 每条导线必须沿着网格线走线，最多只能弯曲一次。即，每条导线要么是一条垂直或水平的直线，要么恰好形成一个 $90$ 度的转弯，构成一个“L”形。导线在路径上的任何位置都不能相互交叉或重叠。 你的任务是确定电源与用电设备之间的一种匹配方案，使得所有导线的总长度最小。

输入由以下几行组成： - 第一行包含三个整数 $W$、$H$ 和 $n$ ($1 \leq W,H \leq 10^8$; $1 \leq n \leq 10^6$)。 - 接下来的 $n$ 行每行包含一个整数 $h_i$ ($1 \leq h_i \leq H$)。 - 接下来的 $n$ 行每行包含两个整数 $x_i$ 和 $y_i$ ($1 \leq x_i \leq W$; $1 \leq y_i \leq H$)。 保证电路板上的每个点最多有一个电源或用电设备。此外，不存在两个用电设备 $i$ 和 $j$ 使得 $x_i = x_j$。

如果在给定约束下无法找到这样的匹配方案，则输出一行，包含 $-1$。 否则，输出一行，包含 $n$ 个用空格分隔的整数。第 $i$ 个整数表示 $p_i$，即电源 $i$ 连接到用电设备 $p_i$。

翻译由 DeepSeek V3 完成