[BOJ/수학] 백준 11644 - 선분과 점 (Java)

11644 - 선분과 점

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

문제

3차원 좌표 평면 위에 선분 하나와 점 하나
선분의 양 끝점: A(Ax, Ay, Az)와 B(Bx, By, Bz)/ 점의 좌표: C(Cx, Cy, Cz)
(x1, y1, z1)과 (x2, y2, z2) 사이의 거리 = $\sqrt{(x2-x1)^2+(y2-y1)^2+(z2-z1)^2}$

=> 선분과 점 사이의 거리의 최솟값?

입력
선분과 점의 좌표 Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz (0 <= 좌표 (정수) <= 10,000)
출력: 선분과 점 사이의 거리의 최솟값
절대/상대 오차 $10^{-6}$까지 허용

---

풀이

• Point 클래스 
  • 3차원 좌표: (x, y, z)
  • 두 점 사이의 거리: `distanceTo()`
  • 선분 AB 위에서 t비율 지점의 좌표 반환: `interploate()`
    • 두 점 A, B가 3차원 공간에 있다고 할 때, A(Ax, Ay, Az)와 B(Bx, By, Bz)
    • 선분 AB 위의 중간 지점: `t = 0.5` / A쪽에 가까움: `t < 0.5` / B쪽에 가까움: `t > 0.5`
    • 위치를 구하는 공식: 선형 보간(linear interploation)
      => P(t) = A + t * (B - A) -> Px = Ax + (Bx - Ax) * t / Py = Ay + (By - Ay) * t / Pz = Az + (Bz - Az) * t

class Point {
    double x, y, z;

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

    double distanceTo(Point p) {
        double dx = this.x - p.x;
        double dy = this.y - p.y;
        double dz = this.z - p.z;
        return Math.sqrt(dx * dx + dy * dy + dz * dz);
    }

    Point interpolate(Point to, double t) {
        return new Point(
                this.x + (to.x - this.x) * t,
                this.y + (to.y - this.y) * t,
                this.z + (to.z - this.z) * t
        );
    }
}

 

삼분 탐색(Ternary Search)

• 볼록/오목 함수에서 최솟값/최댓값을 빠르게 찾기 위한 방법
  볼록 함수: 그래프가 V자처럼 생긴 함수/ 오목 함수: 그래프가 ∧자처럼 생긴 함수
  
  • 극값이 최대 1개 이하로 있는 모든 그래프에서 사용 가능(가장 낮은/높은 점 한 군데 존재)
    • 이분 탐색: 그래프가 단조 증가 or 단조 감소한다는 조건 하에서만 사용 가능
  • 함수가 단조 감소 후 증가(V자 모양) -> 최솟값 찾기
  • 함수가 단조 증가 후 감소(∧자 모양) -> 최댓값 찾기
• 범위를 3등분해서 2개의 점 비교, 1/3지점과 2/3 지점의 함수값 크기 비교 기반 탐색
  • 이분 탐색: 범위를 반으로 나눔
• 어떤 구간 `[low, high]`가 있을 때 중간 두 점
  • `m1 = (2 * low + high) / 3`, `m2 = (low + 2 * high) / 3`
  • 두 점의 함수 값 비교
    • `f(m1) < f(m2)` -> 최솟값이 왼쪽에 있음 => 오른쪽 버림
    • `f(m1) > f(m2)` -> 최솟값이 오른쪽에 있음 => 왼쪽 버림
  • => 계속 구간줄여나가면서 원하는 값 찾기

 

• `t`값을 [0, 1] 구간에서 삼분 탐색
• `p1`, `p2`: 선분 AB 위의 임의의 지점
• `d1`, `d2`: `p1`, `p2`와 C 사이의 거리

double low = 0.0, high = 1.0;
while (high - low > 1e-9) {
    double m1 = (2 * low + high) / 3;
    double m2 = (low + 2 * high) / 3;

    Point p1 = A.interpolate(B, m1);
    Point p2 = A.interpolate(B, m2);

    double d1 = p1.distanceTo(C);
    double d2 = p2.distanceTo(C);

    if (d1 > d2) low = m1;
    else high = m2;
}

Point closest = A.interpolate(B, (low + high) / 2);

---

코드

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

// 선분과 점
class Point {
    double x, y, z;

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

    double distanceTo(Point p) {
        double dx = this.x - p.x;
        double dy = this.y - p.y;
        double dz = this.z - p.z;
        return Math.sqrt(dx * dx + dy * dy + dz * dz);
    }

    Point interpolate(Point to, double t) {
        return new Point(
                this.x + (to.x - this.x) * t,
                this.y + (to.y - this.y) * t,
                this.z + (to.z - this.z) * t
        );
    }
}

public class boj_11664 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        Point A = new Point(
                Double.parseDouble(st.nextToken()),
                Double.parseDouble(st.nextToken()),
                Double.parseDouble(st.nextToken())
        );
        Point B = new Point(
                Double.parseDouble(st.nextToken()),
                Double.parseDouble(st.nextToken()),
                Double.parseDouble(st.nextToken())
        );
        Point C = new Point(
                Double.parseDouble(st.nextToken()),
                Double.parseDouble(st.nextToken()),
                Double.parseDouble(st.nextToken())
        );

        double low = 0.0, high = 1.0;
        while (high - low > 1e-9) {
            double m1 = (2 * low + high) / 3;
            double m2 = (low + 2 * high) / 3;

            Point p1 = A.interpolate(B, m1);
            Point p2 = A.interpolate(B, m2);

            double d1 = p1.distanceTo(C);
            double d2 = p2.distanceTo(C);

            if (d1 > d2) low = m1;
            else high = m2;
        }

        Point closest = A.interpolate(B, (low + high) / 2);
        System.out.printf("%.10f\n", closest.distanceTo(C));
    }
}