ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2629 - Manhattan

問題
提出コード

解法

考えられるパターンは2つあります。
1つは三平方の定理を使うパターン、もう1つは台形を考えるパターンです。

  1. 三平方の定理を使うパターン
    出発地点を座標(0,0)として到着地点を(x,y)とすると、求める答えはx+yの最大値になります。
    また、(x,y)の考えられるパターンは、半径dの円周であるため、x^{2}+y^{2} = d^{2}が成り立ちます。このときのx+yの最大値は \sqrt{2}dになります。

  2. 台形を考えるパターン
    サンプルケースの1つめを見ればわかるように、x軸を行って戻ってくるようなパターンが考えられます。
    f:id:emtubasa:20180925235734p:plain
    上の図のような太線部分が通る場所になります(斜めの線がdになります)。このとき、最短距離を求めなければならないので、上の横線と下の横線の和がちょうど1になるときが最大値が最も大きくなるパターンになります。
    そしてこのときの縦の長さは、dを切り捨てで整数になおしたものになります。
    ということでこのケースは、dを切り捨てで整数に直したあと1を加えたものが答えになります。

    ということで、この2パターンのうち、大きい方が答えになります。