AOJ 2629 Manhattan (JAG 夏合宿 2014 day2-A) (250 点)

伝説のりんごさんセットの 1 問目

• 問題へのリンク

問題概要

二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。

道路上の 2 点 のユークリッド距離が実数 で与えられる。

点 から道路のみを通って、点 へと到達する最短経路長として考えられる最大値を求めよ。

制約

• (小数点 3 桁まで)

考えたこと

以下の 2 つの場合に場合分けする (それ以外は対称性から除外)

• の 座標がともに整数である場合
• の 座標が整数で、 の 座標が整数である場合

前者については、下図のような感じ。 として、 が答えとなる。

後者については、直角三角形の斜辺の長さが となるような設定となる。つまり、

• という制約下で、
• の最大値を求める問題

と言える。これは不等式

　(等号成立は のとき)

に着目すると、 で最大となることがわかる。つまり直角二等辺三角形になる場合である。よって が答え。

前者と後者のうちの大きい方が最終的な答えとなる。

#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-9;
int main() {
    double d, res = 0;
    cin >> d;
    res = max(res, d * sqrt(2.0));
    long long D = (long long)(d + EPS);
    res = max(res, D + 1.0);
    cout << fixed << setprecision(10) << res << endl;
}