P15881 [ICPC 2026 NAC] Gemstone Dowsing

**寻石** 是一种在自然环境中寻找珍贵岩石和宝石的爱好。作为国家级寻石爱好者，你决心要找到尽可能珍贵的宝石！ 你发现了一块区域，其横截面可以用二维欧几里得平面建模，地面位于直线 $y = 0$ 处。这条线以下全是坚固的岩石，以上全是空气。岩石中埋藏着 $N$ 颗稀有宝石，每颗宝石位于一个（可能不唯一）的 $(x, y)$ 位置，其中 $y < 0$。 其中一些宝石已经被其他寻石者追踪过，他们通过公布宝石的位置来宣告自己的发现（但宝石本身仍留在原处）。这为你留下了一些尚未被发现的宝石！ 为了实际找到宝石，你计划使用一台 **示波器** 来检测每颗宝石发出的波形。每颗宝石都有唯一的频率，可以从一定距离外测量到；然而，这台示波器有一个特殊之处：每次使用时，它只记录 **距离最近的宝石** 所发出的频率，距离采用欧几里得距离度量。如果出现平局，它会在距离最近的宝石中任意选择一个频率进行记录。 :::align{center}  样例输入 1 的示意图。地下的宝石图标表示已被发现的宝石，地面上的点表示你的示波器读数。 ::: 你刚刚在地球表面的多个 **不同** 位置 $(x_j, 0)$ 上使用了这台示波器 $N$ 次。你记录了这些位置以及在该位置示波器检测到的频率 $f_j$。有趣的是，你注意到 **每颗宝石的频率在你的记录中恰好出现一次**。 在尚未被其他寻石者发现的宝石中，你想找到最有价值的那一颗。当然，宝石埋得越深，价值就越高！ 一个 **合理配置** 是指将每颗未被发现的宝石放置在二维欧几里得平面上的一个位置，使得满足以下条件： - 每颗宝石都位于地下（$y < 0$）； - 对于位置 $(x_j,0)$ 上每个频率为 $f_j$ 的示波器读数，没有任何宝石在欧几里得距离上比频率为 $f_j$ 的那颗宝石更靠近 $(x_j,0)$。 对于每颗尚未被发现的宝石，你想计算在所有合理配置中，该宝石可能达到的最深（即最负的）$y$ 坐标。

第一行包含两个空格分隔的整数 $N$ $(2 \le N \le 10^5)$ 和 $K$ $(1 \le K \le N - 1)$：分别表示埋藏的宝石数量（同时也是示波器读数的数量）以及已经被其他寻石者发现的宝石数量。 接下来的 $K$ 行，每行包含三个空格分隔的整数 $x_i$ $(|x_i| \le 10^6)$、$y_i$ $(-10^6 \le y_i < 0)$ 和 $f_i$ $(1 \le f_i \le N)$，描述了一颗已被发现的宝石的位置和频率。有可能两颗或多颗宝石位于同一位置。保证 $f_i$ 的值互不相同。 最后 $N$ 行，每行包含两个空格分隔的整数 $x_j$ $(|x_j| \le 10^6)$ 和 $f_j$ $(1 \le f_j \le N)$，描述了一次示波器读数。保证 $x_j$ 的值互不相同，且按递增顺序给出，并且每颗宝石（无论是已发现还是未发现）都恰好对应一次示波器读数。同时保证至少存在一种合理的宝石配置。

对于 $N-K$ 颗尚未被发现的宝石，每行输出一个整数和一个负实数：宝石的频率 $f_\ell$ 以及在所有合理配置中该宝石可能达到的最深（最负的）$y$ 坐标 $y_\ell$。可以证明，对于每颗未被发现的宝石，这个最深可能 $y$ 坐标存在且为负有限值。 你可以按任意顺序输出这些行。 如果你的答案为每个未发现宝石分配的深度值与标准答案的绝对误差或相对误差不超过 $10^{-5}$，则视为正确。

翻译由 DeepSeek V3.2 完成