P13748 [NWERC 2024] Jib Job

在去年的无限墙建设取得成功后，Bob 被雇佣到一个新的工地工作。 他的第一个任务是在新的工地上安装多台起重机。 :::align{center}  Pixabay Content Licence by tonisun on [Pixabay](https://pixabay.com/photos/cologne-construction-5511439/) ::: 每台起重机由一个中央塔楼和一个水平的横梁（称为“臂架”）组成，臂架安装在塔楼顶部，可以自由地绕塔楼旋转。 塔楼的位置和高度已经为 Bob 安装好了，坐标和高度都是固定的。 现在只需要安装臂架。 不过，Bob 在安装时需要注意以下几点： 首先，臂架的长度不能超过其塔楼的高度，否则起重机会倾倒。 其次，臂架的长度必须是正整数米。 第三，任何两台起重机都不能发生碰撞。 幸运的是，所有塔楼的高度都不相同。 因此，唯一可能发生碰撞的情况是，一台起重机的臂架撞到了另一台起重机的塔楼。 注意，臂架仅仅接触到另一台塔楼并不会导致碰撞。 :::align{center}  图 J.1：样例输入 3 的示意图。每个圆心的数字表示该位置起重机的高度，每个箭头的数字表示该起重机臂架的长度。 ::: 在此基础上，Bob 希望最大化至少被一台起重机覆盖到的区域面积，也就是说，最大化通过旋转臂架，至少有一台起重机的臂架可以覆盖到的地面点的面积。 你应该为每台起重机选择多长的臂架，才能使被覆盖的面积最大？

输入包含： - 一行一个整数 $n$（$1\leq n\leq500$），表示起重机的数量。 - 接下来 $n$ 行，每行三个整数 $x$、$y$ 和 $h$（$0\leq x,y\leq 10\,000$，$1\leq h\leq 10\,000$），表示一台起重机的位置和高度，单位为米。 保证没有两台起重机的位置相同，且所有高度都不同。

对于每台起重机，输出其臂架的正整数长度（单位为米），使得被覆盖的面积最大。 如果有多组最优解，输出任意一组均可。

由 ChatGPT 4.1 翻译