第2回早稲田大学プログラミングコンテスト

I - その味は甘くて


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 512MB

 突然だが,あなたはとある養蜂家専属のプログラマである.ある日,巣で生成されるハチミツの糖度を管理するために,次のようなプログラムを作成するよう求められた.

問題

 下図のような正六角形が敷き詰められた座標系を考える.
図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における巣の様子

Submit提出する