AOJ 2629 - Manhattan
解法
考えられるパターンは2つあります。
1つは三平方の定理を使うパターン、もう1つは台形を考えるパターンです。
三平方の定理を使うパターン
出発地点を座標(0,0)として到着地点を(x,y)とすると、求める答えはx+yの最大値になります。
また、(x,y)の考えられるパターンは、半径dの円周であるため、が成り立ちます。このときのx+yの最大値はになります。台形を考えるパターン
サンプルケースの1つめを見ればわかるように、x軸を行って戻ってくるようなパターンが考えられます。
上の図のような太線部分が通る場所になります(斜めの線がdになります)。このとき、最短距離を求めなければならないので、上の横線と下の横線の和がちょうど1になるときが最大値が最も大きくなるパターンになります。
そしてこのときの縦の長さは、dを切り捨てで整数になおしたものになります。
ということでこのケースは、dを切り捨てで整数に直したあと1を加えたものが答えになります。
ということで、この2パターンのうち、大きい方が答えになります。