ヤマカサのプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.172 UFOを捕まえろ

高校数学チックな問題?

No.172 UFOを捕まえろ - yukicoder ちょっと頭を使う問題だと思います。

解き方

円の中心の座標  p

 p = (a, b)

とします。また、 a \geq 0,  b \geq 0を満たすとします。これは、UFOの位置を第1象限のみを考えても一般性を失わないためです。円の中心が第1象限に存在していることから、結解の直線の方程式は、

 y = - x + k   ①

 k \gt 0

を考えれば良いことが分かります。 k の値を求めることが題意になります。

ここで、半径  r で中心が原点の円を考えます。このとき、①と原点の円が接する条件は、円と直線の方程式が共有点を一つもつことになります。下のサイトが参考になります。

円と直線の位置関係

したがって、

 x^2 + y^2 = r^2

から、

 x^2 + (-x + k)^2 = r^2

 2x^2 - 2kx + k^2 - r^2 = 0

上の方程式の判別式を  D とすると、

 D = - k^2 + 2r^2

となり、 k に関する方程式が重解を持てばよいので、 k \gt 0 から

 k = \sqrt {2}r

となります。以上より、原点に円が存在するとき、その結解の方程式は

 y = - x + \sqrt {2}r

となることが分かりました。

この方程式を x 軸方向に  a y 軸方向に  b だけ平行移動させれば良いので、

求める結解の方程式は、

 y = - x + a + b + \sqrt{2}r

となります。 k は整数であることから、

 k = a + b +\sqrt{2}r

を切り上げた値となります。

マンハッタン距離に関する動画

東北大学の学生のプレゼンテーションで距離に関するものがあったので、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);
    }
}