题目描述
在去年成功建造了一堵无限长的墙后,Bob 被雇佣来完成一项新任务。他的第一个任务是在一个新的建筑工地上安装多台起重机。
每台起重机由一个中央塔和一个水平臂(吊臂)组成,吊臂可以围绕中央塔自由旋转。塔已经为 Bob 安装完毕,位置和高度都已固定。现在只需要安装吊臂。然而,Bob 需要小心处理这个问题。首先,吊臂的长度不能超过塔的高度,否则起重机会倾倒。其次,吊臂的长度必须是正整数(以米为单位)。第三,任何两台起重机都不能发生碰撞。幸运的是,所有塔的高度都不同,因此两台起重机发生碰撞的唯一可能是一台起重机的吊臂撞到另一台起重机的塔。注意,吊臂碰到另一台起重机的塔并不算碰撞。
考虑到这些,Bob 希望最大化至少一台起重机可以覆盖的区域面积,即地面上至少有一台起重机的吊臂可以通过旋转覆盖到点的面积最大。Bob 应该如何选择每台起重机的吊臂长度,以最大化覆盖面积?
输入格式
一行,包含一个整数 $n( 1 \leq n \leq 500)$,表示起重机的数量。
$n$ 行,每行包含三个整数 $x, y$ 和 $h( 0 \leq x, y \leq 10000, 1 \leq h \leq 10000 )$,表示起重机的位置和高度(以米为单位)。
保证没有两台起重机位于同一位置,且所有高度都不同。
输出格式
对于每台起重机,输出其吊臂的正整数长度(以米为单位),使得覆盖面积最大化。
如果有多个最优解,可以输出其中任意一个。
样例输入 #1
3
1 1 4
4 1 5
7 4 3
样例输入 #2
3
0 0 10
4 6 8
6 6 6
样例输入 #3
5
2 6 2
4 10 4
5 6 6
8 8 7
10 2 8