No.172 UFOを捕まえろ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 221
作問者 : threepipes_sthreepipes_s

10 ProblemId : 388 / 出題時の順位表

問題文

ゆきちゃんは愛犬ルビーと一緒に日課の散歩中。
しかし突如現れたUFOが、ルビーをさらって逃げてしまった。
ルビーを助けるため、ゆきちゃんの超能力を発揮させてUFOを捕まえろ!

座標$(0, 0)$にいるゆきちゃんは超能力によって、境界までのマンハッタン距離が自然数である結界を瞬時に作ることができる。
UFOは現在位置$(x, y)$、半径$r$の円であり、結界を作ったときにUFOが結界内部にいる場合、確保が成功する。
このとき、作った結界にUFOが触れていると逃げられてしまうので注意が必要だ。(※)

ゆきちゃんは他のUFO襲来にも備えて力を温存するため、結界の大きさは最小限にとどめたい。
UFOを確保するために作る結界サイズの最小値を出力せよ。


※結界は十分に薄いので、UFOが境界に触れているとは次の状態を指す。
UFOの境界上または内部に含まれ、かつ結界の境界上に位置するような点Pが存在する状態。

入力

x y r

入力は1行で与えられる。
UFOは座標$(x, y)$に存在し、その半径は$r$である。
各入力の制約は以下の通りで、入力はすべて整数である。
$-100\le x\le100$
$-100\le y\le100$
$1\le r\le100$

また、ゆきちゃんのいる座標は$(0, 0)$である。

出力

ゆきちゃんが作る結界の大きさ(ゆきちゃんから境界までのマンハッタン距離)を1行で出力せよ。

サンプル

サンプル1
入力
2 2 1
出力
6

境界までマンハッタン距離6の結界を作ることで、UFOを結界の内側に閉じ込めることができます。
ゆきちゃんは座標(0, 0)にいるので、結界(緑)、UFO(赤)は以下の図のようになります。

サンプル2
入力
-50 -40 30
出力
133

かなり遠くまで逃げたUFOですが、ゆきちゃんの手によってすぐに捕まってしまいます。

サンプル3
入力
0 0 100
出力
142

残念ながら、UFOは逃げる間もなくゆきちゃんに捕まってしまいました。

提出ページヘ