AOJ 2629 Manhattan

問題

Manhattan | Aizu Online Judge

解法

一方の点 A は x 軸と平行な直線の上に乗せて考えても問題ありません。こうすると, もう一方の点 B の位置によって場合分けができます。

B が y 軸と平行な直線の上に乗せられている場合
この場合は, A の位置をうまく調整すると, x0 + sqrt(d^2-x0^2) の最大値を取れば良いことが分かります。x0 について偏微分して = 0 になるところは x0 = d/sqrt(2) であることがわかるので, それで計算しましょう。

B が x 軸と平行な直線の上に乗せられている場合
d の整数部分だけ y 方向に進む ということをやったあと, x 軸方向に合計 1 稼ぐ, ということをできます(図)。

これらの中で最大のものが答えです。

int main() {
    double d;
    cin >> d;
    int d1 = d*1000;
    double ans = sqrt(2)*d;
    ans = max<double>(ans, (int)(d)+1);
    printf("%.10lf\n", ans);
    return 0;
}