[yukicoder] No.172 UFOを捕まえろ
高校数学チックな問題?
No.172 UFOを捕まえろ - yukicoder ちょっと頭を使う問題だと思います。
解き方
円の中心の座標 を
とします。また、, を満たすとします。これは、UFOの位置を第1象限のみを考えても一般性を失わないためです。円の中心が第1象限に存在していることから、結解の直線の方程式は、
①
を考えれば良いことが分かります。 の値を求めることが題意になります。
ここで、半径 で中心が原点の円を考えます。このとき、①と原点の円が接する条件は、円と直線の方程式が共有点を一つもつことになります。下のサイトが参考になります。
したがって、
から、
上の方程式の判別式を とすると、
となり、 に関する方程式が重解を持てばよいので、 から
となります。以上より、原点に円が存在するとき、その結解の方程式は
となることが分かりました。
この方程式を 軸方向に 、 軸方向に だけ平行移動させれば良いので、
求める結解の方程式は、
となります。 は整数であることから、
を切り上げた値となります。
マンハッタン距離に関する動画
東北大学の学生のプレゼンテーションで距離に関するものがあったので、YouTubeのリンクを張ります www.youtube.com
コード
import java.util.Scanner; public class Exec0172 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int x = scan.nextInt(); int y = scan.nextInt(); int r = scan.nextInt(); scan.close(); if(x < 0) { x = - x; } if(y < 0) { y = - y; } int k = x + y + (int)(Math.sqrt(2) * r) + 1; System.out.println(k); } }