AOJ 2629 : Manhattan

問題文 : Manhattan

めちゃくちゃ時間を書けたので思考の整理に解法をまとめます。

解法 :

ほとんどのケースで答えは $\sqrt{2} d$ になります。座標の関係でこれが答えにならないケースも有りますがそれは後述します。
これを確かめるために, すぬけ君の家の座標を $(x,\ 0)$, すめけ君の家の座標を $(c,\ \sqrt{d^2 - (c - x)^2})$ としましょう。(ここで $c$ はある整数)
対称性から, $x \geqq c \geqq 0$ として考えても構わないことが分かります。この条件で問題文で与えられた距離

$D = x - c + \sqrt{d^2 - (c - x)^2}$

を最大化します。 $\dfrac{dD}{dx} = 0$ を解いて $x = c + \dfrac{d}{\sqrt{2}}$ が導かれます。$D$ に $x = \dfrac{d}{\sqrt{2}}$ を代入すると $D = \sqrt{2} d$ を得ます。 これより $D$ の最大値は $c$ によらず $\sqrt{2} d$ となります。

ちなみにこんなことをしなくても, 斜辺 $d$ の三角形の残りの二辺の長さを最大化することを考えると, 頂角が 90 度の二等辺三角形が出てくる気が(これを書いている間に)してきました。悲しいです。

$d \geqq 1$ のとき, $D = \sqrt{2} d$ が答えにならないケースがあります。問題文中のサンプル 1 のようなケースです。これは, $D$ が上述の式で表せないために起こるケースです。
すぬけ君が原点にあったとして, すめけ君の家の $x$ 座標が整数, $y$ 座標が $[0, 1)$ の範囲に収まったとすると, すぬけ君とすめけ君の家の $y$ 座標を適切に平行移動することによって $D$ を $|\text{smeke}_x| + 1$ にすることが可能です。こうなる $x$ があるかどうかは $x = 1$ から $x = 10$ を全探索することで見つけることができます。

コード

#include <bits/stdc++.h>

using namespace std;

int main()
{
	double d;
	scanf("%lf", &d);

	double ans = d * sqrt(2);

	for (int x = 1; x <= 10; x++){
		if (d * d - x * x >= 0){
			double y = sqrt(max(0.0, d * d - x * x));
			ans = max(ans, x + (y < 1.0 ? 1.0 : y));
		}
	}

	printf("%.10lf\n", ans);

	return (0);
}