우주 정거장

 

[문제] 

 선분(line segment) 모양의 우주 정거장 S=(A, B)가 있다. 우주 정거장의 시작점과 끝점은 3차원 좌표 A와 B이다. 우리는 점 P(x, y, z)에 존재하는 인공위성에서 우주 정거장 S에 이르는 가장 짧은 길이의 연결 통로 T를 건설하려고 한다. 이를 위해 점 P(x, y, z)와 선분 S를 연결하는 통로 T의 최소 정수 길이 L이 필요하다. 즉 T의 실제 길이가 34.56018이라면 정답 L은 이를 올림 한 35가 되어야 한다.

점 P에서 S에 가장 가까운 점은 선분 S 위에 존재한다. 선분 S 상에 존재하는 모든 점은 아래 직선의 방정식으로부터 parametric 한 방식으로 만들어 낼 수 있다. 이는 t=0일 때 A, t=1일 때 B, t=1/2일 때 A와 B의 중점이 된다. 예를 들어 A(5, 9, -13), B(-5, 11, 7)에서 t=0.5이면 그 점은 (0, 10, -3)이고 t=0.78이면 (2.8, 9.44, -8.6)이 된다.

S(t) = t * B + (1-t) * A

 

[입출력]

 입력 파일 station.inp의 3개 줄에 우주 정거장 S의 두 끝 점 A, B와 인공위성 P(x, y, z)의 좌표가 3개 정수로 주어진다. 각 좌표는 모두 정수이며 그 범위는 -10,000 <= x, y, z <= 10,000이다. 여러분은 P에서 S에 이르는 연결 통로 T의 길이보다 큰 최소 정수 L을 계산하여 출력 파일 station.out에 출력해야 한다. 예를 들어 연결 통로 T의 실제 길이가 14.0923이라면 정답은 15가 되어야 하고, 만일 정확하게 그 길이가 156.0이라면 답은 156이 된다.

 

[예제]

station.inp

50  50  50  // A 좌표

0    0    0  // B 좌표

10  -6  30 // P 좌표

station.out

26

 

station.inp

 700 -940 -854

-390  619  340

    3  907   -17

station.out

577

 

[수학적 방정식을 이용한 풀이]

 교수님의 힌트를 참고하여 3가지 경우로 나누어 풀었다. (Divide and Conquer)

1. 그림에서의 P2처럼 선분 S의 A 부분과 둔각을 이루어 가장 가까운 지점이 A 인 경우.

2. 선분 S의 B 부분과 둔각을 이루어 가장 가까운 지점이 B 인 경우.

3. 선분 S의 A와 B부분 모두 예각을 이루어 선분 S와 수직선이 가장 짧은 선인 경우.

 

(cosθ = 두 벡터의 내적 / 각 벡터의 길이의 곱) 을 이용하여 cosθ를 구하고, cosθ가 양수냐 음수냐에 따라 예각인가 둔각인가를 구분하며 case를 divide 하였다. 어느 한 각이 둔각이라면 둔각 쪽의 선분 S의 끝과 P의 거리가 가장 짧은 거리다. 하지만, 두 각이 모두 예각이라면 직선의 방정식을 이용해 점과 직선 사이의 거리를 계산하여 구하거나, binary search를 이용하여 가장 짧은 거리를 찾아내야 한다. 교수님은 binary search 방식을 권장하셨다. 나는 직선의 방정식을 이용하여 풀었다.

 

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

sak5010/PNU_Algorithm_2020

 

[binary search를 이용한 학생 풀이]

 다른 학생이 푼 코드를 조금 수정하여 풀어보았다. 교수님이 말씀하신 대로, 직선의 방정식을 이용하여 푸는 것이 아닌 binary search를 이용하여 가장 짧은 직선의 길이를 탐색하는 divide and quanquer 방식을 이용하여 풀었다.

이 코드에서 핵심 함수는 mdist인데, 재귀함수로 작성되었다. 함수에 들어오면 제일 먼저 중점을 찾고, 점 p와 a의 거리, 점 p와 b의 거리를 계산한다. 만약 선분 ap와 선분 bp가 거리가 같다면(물론 정수로 올림 한 값이 기준이다) 가장 짧은 선은 선분 S의 중점과 점 p 사이의 거리일 것이므로 탈출 조건이 된다. 선분 ap와 선분 bp의 거리가 같지 않다면 거리가 짧은 쪽만 보면 되므로 거리가 긴 쪽 절반은 버리고 짧은 쪽 절반만 다시 재귀 함수로 들어가 탐색한다. 이렇게 계속하다 보면 정수 올림 때문에 선분 p와 왼쪽의 거리, 선분 p와 오른쪽의 거리가 같아질 때가 오는데, 이때가 가장 짧은 직선이 되는 것이다.

 

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

sak5010/PNU_Algorithm_2020

 

[binary search를 이용한 조교 풀이 (feat. ε) ]

 조교님이 푼 코드를 조금 수정하여 풀어보았다. 바로 위 코드와 같이 binary search를 사용하여 푼다. 다른 점은, t의 방정식을 이용하여 점의 위치를 파악한다는 것과, 입실론을 사용한다는 것이 다르다. 이 코드에서 핵심 함수는 search 함수인데, 함수에 들어오면 주어진 t범위의 중간점을 찾고 만약 왼쪽 끝에서 입실론 만큼 오른쪽 이동 했을때 오른쪽 끝을 넘어간다면 범위가 좁아질대로 좁아졌으므로 탈출조건이 된다. 그렇지 않다면 왼쪽으로 살짝 이동한 점과의 거리와 오른쪽으로 살짞 이동한 점과의 거리를 비교하여 가장 짧은 값을 찾는다. 만약 오른쪽 길이가 더 짧다고 한다면 왼쪽 절반은 버리고 오른쪽 절반을 기준으로 중점을 찾아 다시 재귀하는 형식으로 짧은 선을 찾아 나간다.

 

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

sak5010/PNU_Algorithm_2020

 

[binary search를 이용한 풀이]

 공부 후 다시 풀어보았다. 위 조교 코드와 거의 같다.

 

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

sak5010/PNU_Algorithm_2020