[백준] 11664번 선분과 점 Java

문제 링크

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

문제

3차원 좌표 평면 위에 선분 하나와 점 하나가 있다. 선분의 양 끝점은 A(Ax, Ay, Az)와 B(Bx, By, Bz)로 나타낼 수 있다. 점의 좌표는 C(Cx, Cy, Cz) 이다.

선분과 점 사이의 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 선분과 점의 좌표 Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz가 주어진다. 좌표는 0보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

첫째 줄에 선분과 점 사이의 거리의 최솟값을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

알고리즘: 삼분 탐색

풀이

A와 B점 사이의 점 중에서 C와 연결했을 때 최소가 되는 점을 찾아야 한다. 삼분 탐색으로 찾는데
먼저 A와 B점의 mid점을 구한다.
|CA - CB| <= 0.000001 일 때 CMID값을 출력하고, 그렇지 않다면 CA와 CB를 비교하고,
더 긴 길이를 가진 선분의 점에 MID를 대입해준다. ex) CA가 더 길면 -> A = MID
왜냐하면 CA가 더 길다고 가정하면 MID부터 A점들을 각각 C와 연결했을 때 그 모든 선분은 CMID보다 길기 때문에 범위에서 제외해야 함
위 방법을 |CA - CB| <= 0.000001 이 조건이 만족할 때까지 반복해준다.

소스 코드

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

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

public class Main {
    static Point A;
    static Point B;
    static Point C;
    static double ans;
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=0; i<3; i++) {
          double nx = 0;
          double ny = 0;
          double nz = 0;
          for(int j=0; j<3; j++) {
              if(j==0) nx = Double.parseDouble(st.nextToken());
              else if(j==1) ny = Double.parseDouble(st.nextToken());
              else nz = Double.parseDouble(st.nextToken());
          }
          if(i==0) A = new Point(nx, ny, nz);
          else if(i==1) B = new Point(nx, ny, nz);
          else C = new Point(nx, ny, nz);
      }
      //삼분 탐색
      while(true) {
          double CA = Math.sqrt(Math.pow(C.x - A.x, 2) + Math.pow(C.y - A.y, 2) + Math.pow(C.z - A.z, 2));
          double CB = Math.sqrt(Math.pow(C.x - B.x, 2) + Math.pow(C.y - B.y, 2) + Math.pow(C.z - B.z, 2));
          Point mid = new Point((A.x + B.x)/2, (A.y + B.y)/2, (A.z + B.z)/2);
          if(Math.abs(CA - CB) <= 0.000001) {
              ans = Math.sqrt(Math.pow(C.x - mid.x, 2) + Math.pow(C.y - mid.y, 2) + Math.pow(C.z - mid.z, 2));
              break;
          }
          if(CA <= CB) {
              B = mid;
          } else {
              A = mid;
          }
      }
      System.out.println(Math.floor(ans*10000000000.0)/10000000000.0);
    }
}