[백준] 11664번 선분과 점

문제 설명

https://www.acmicpc.net/problem/11664

문제 풀이

• 이분 탐색을 좀 변형하여 풀이하였다.
• lo = A좌표, hi = B좌표로 둔 후에 이분탐색을 진행하되 아래 조건대로 진행하였다.

  (lo -> C거리) < (hi -> C 거리) 일 경우 : hi = mid 좌표
  (lo -> C거리) > (hi -> C 거리) 일 경우 : lo = mid 좌표

• lo != hi 일때까지 위를 반복하면 점과의 거리가 최소인 선분위의 점으로 수렴하게 된다.
• 소수점 계산으로 인해 lo != hi 조건이 무한반복 될 수 있으므로 루프 횟수를 제한했다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static Point A, B, C;

    public static class Point {
        double x, y, z;

        public Point(double x, double y, double z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        @Override
        public boolean equals(Object p) {
            return this.x == ((Point)p).x && this.y == ((Point)p).y && this.z == ((Point)p).z;
        }
    }

    public static double dist(Point a, Point b) {
        return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2) + Math.pow(a.z - b.z, 2));
    }

    public static double solve() {
        Point S = A;
        Point E = B;
        int cnt = 0;

        while(!S.equals(E)) {
            if (++cnt == 100000) break;
            Point mid = new Point((S.x + E.x) / 2, (S.y + E.y) / 2, (S.z + E.z) / 2);

            if (dist(S, C) < dist(E, C)) E = mid;
            else S = mid;
        }
        return Math.round(dist(S, C) * 10000000000.0) / 10000000000.0;
    }

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        A = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        B = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        C = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(solve() + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}