정거장 통로

[문제] 긴 막대(segment) 모양의 우주 정거장 2개 S1 = (A, B), S2 = (C, D)가 있다. 이 두 우주 정거장을 연결하는 가장 짧은 길이의 연결 통로 T를 건설하려고 한다. 우주정거장 문제에서는 점과 선분과의 거리를 계산했다면, 이번 문제는 두 개의 선분 간의 최단 거리를 계산해야 한다. 즉 T는 S1과 S2를 연결하는 최소 정수 길이의 선분이 되어야 한다. 경우에 따라서는 정거장의 끝 점이 통로의 시작과 끝 점이 될 수도 있다.

[입출력] 입력 파일 stube.inp 의 4개 줄에 두 우주 정거장의 끝 점 A, B, C, D의 각 좌표 (x, y, z)가 3개 정수가 주어진다. 각 좌표의 범위는 -10,000 <= x, y, z <= 10,000이다. 여러분은 두 선분의 연결을 보장하는 통로의 최소 정수 길이를 계산하여 stube.out에 출력해야 한다. 예를 들어 연결 통로 T의 길이가 14.0923 라면 정답은 15, 156.0이라면 답은 156이 되어야 한다.

 

[예제]

stube.inp

350   150   350   // A 좌표

   0     0      0    // B 좌표

  10   -6     30    // C 좌표

  56   21    120   // D 좌표

stube.out

20

 

[풀이]

 우주 정거장에서 사용하였던 함수들을 사용하여 해결하였다. 저번 문제와 다른 점은, 우주 정거장 문제에서는 3차원 공간에서 점과 직선 사이의 가장 짧은 거리를 구하는 문제였는데 이번 문제는 3차원 공간에서 직선과 직선 사이의 가장 짧은 거리를 구하는 문제였다. 마찬가지로 binary search를 이용하여 문제를 풀었는데, 우주 정거장 문제에서 사용한 점과 직선 사이의 가장 짧은 거리를 구하는 함수를 선분 간 번갈아 가며 실행 하였다. 예를 들어, 선분AB와 선분CD 사이의 가장 짧은 선분의 길이를 구할때, 선분AB에서 선분CD의 아무 점(나는 점C를 선택했다)과의 가장 짧은 거리를 구하고, 그 가장 짧은 선분이 걸치고 있는 선분AB 위의 점과 선분CD 사이의 가장 짧은 선분의 거리를 구하고 또 그 가장 짧은 선분의 선분CD에 걸쳐져 있는 점과 선분AB사이의 거리를 구하고.. 이 작업을 반복하여 만약 결과가 연속으로 같은 값이 나온다면 그 값이 두 선분 사이의 가장 짧은 거리라는 알고리즘을 사용하여 해결하였다. 이 문제를 풀면서 가장 많이 고생한 점은, 입실론 값을 얼마나 줘야 하는가가 가장 문제였다. 입실론을 얼마나 크고 작게 주느냐에 따라서 무한루프를 도느냐, logical error가 발생하느냐 등 문제가 생기거나 올바른 답이 나오는 경우가 있었다.

https://github.com/sak5010/PNU_Algorithm_2020/blob/master/stube.cpp

sak5010/PNU_Algorithm_2020