← 返回题目列表

AtCoder · wupc_09

I. 味道是甜的

中文机器翻译题面 查看原题
 突然之间,你成为了一名专门为某个养蜂人工作的程序员。有一天,我被要求编写以下程序来控制蜂巢中生产的蜂蜜的糖含量。

問題

 考虑一个充满正六边形的坐标系,如下图所示。
图1:填充正六边形的坐标系

 有关蜂窝的信息在指定的坐标系上给出。蜂箱由蜂箱类型、中心坐标和大小组成。燕窝中所含六边形的糖含量因燕窝类型而异。
     
  • 类型 1:巢中包含的所有六边形中糖含量均匀 添加了 1 。
  •  
  • 类型 2:尺寸 n,距中心的距离 d 然后糖含量 n-d 。
  •  
  • 类型 3:尺寸 n,距中心的距离 d 然后糖含量 (n-d)^2 。
 
 例如,如果尺寸为 3 每种巢穴中包含的六边形的糖含量如下图所示添加。

图 2:每种类型 3 个巢穴的大小

 如果一个六边形包含在多个巢中,则该部分的糖含量将为每个巢的糖含量之和。输出含糖量最高的部分的含糖量。

入力

输入将以以下格式从标准输入给出。
N
type_{1} x_{1} y_{1} size_{1}
type_{2} x_{2} y_{2} size_{2}
...
type_{N} x_{N} y_{N} size_{N}
  • 1 蜂箱数量在行中 给出了 N(1 ≦ N ≦ 10,000)。
  • 2 行目~ N+1 每个巢的信息在行中 1 逐行给出。
  • 每个巢的信息类型为 ( type_{i} ),中心座標( x_{i},y_{i} ),和尺寸( size_{i} ),每个以半角空格分隔。另外,各自满足以下条件。
    • 1 ≦ type_{i} ≦ 3
    • |x_{i}| ≦ 500
    • |y_{i}| ≦ 500
    • 1 ≦ size_{i} ≦ 500

出力

含糖量最高的六边形的含糖量1 行上输出。
请在末尾输出换行符。

部分点

10 对于点,除了输入条件外,还满足以下所有条件。
  • 1 ≦ N ≦ 100
  • type_{i} = 1
  • |x_{i}| ≦ 100
  • |y_{i}| ≦ 100
  • 1 ≦ size_{i} ≦ 100

50 对于点,除了输入条件外,还满足以下所有条件。
  • type_{i} = 1


入力例 1

1
1 0 0 3

出力例 1

1

入力例 2

1
3 -1 -1 4

出力例 2

16
3 号、4 号燕窝的最大糖含量为 16 。

入力例 3

2
1 0 0 3
3 -1 -1 4

出力例 3

17
如果多个巢重叠,则该区域的糖含量是每个巢的糖含量之和。

入力例 4

3
1 0 0 2
1 1 -1 2
1 -1 1 2

出力例 4

3
巢如下图所示。
图 3:输入示例 4 中嵌套的外观