[문제]
막대(segment) 모양의 우주 정거장 2개 $S_1 = (A,B)$, $S_2 = (C,D)$ 가 있다. 이 두 우주 정거장을 연결하는 연결 통로(tube) $T$를 건설하려고 한다. 단, 우주에서의 공사작업은 매우 큰 비용이 들기 때문에 $T$의 길이는 최소화하려고 한다. 즉, $T$는 $S_1$과 $S_2$를 연결하는 최소 정수 길이의 선분이 되어야 한다. 정거장의 끝점이 통로의 연결점이 될 수도 있다.
[입출력]
입력 파일 station.inp 의 4개 줄에 두 우주 정거장의 끝 점 $A,B,C,D$ 의 각 3차원 좌표 $(x, y, z)$가 3개 정수로 주어진다. 각 좌표의 범위는 $-10000 \leq x, y, z \leq 10000$이다. 여러분은 두 정거장을 연결하는 통로의 최소 정수 길이를 계산하여 station.out에 출력해야 한다. 예를 들어 연결 통로 $T$의 길이가 14.0923 라면 15, 156.0이라면 156으로 출력해야 한다.
[예제]
|
station.inp |
station.out |
|
350 150 350 // A 좌표 0 0 0 // B 좌표 10 –6 30 // C 좌표 56 21 120 // D 좌표 |
20
|
|
700 -940 -854 -390 619 340 3 907 -17 111 222 333 |
305
|
|
0 0 0 0 10000 10000 0 5000 5000 5000 5000 5000 |
0
|
[풀이] $O(1) or O(\log_210000)$
$O(1)$의 풀이는 고등학교 수학 문제다. 선분 $AB$와 $pq$, $CD$와 $pq$가 각각 직교한다는 점은 직관적으로나 수학적으로나 자명하기 때문에, 내적/외적을 적절히 사용해서 정사 시키고.. 난리 치면 풀린다. 선분이라는 점이 약간 까다로우나, 선분에 대해서도 구글 검색 시 코드가 나오므로 생략.
$O(\log_210000)$풀이는 생각보다 어렵고, 생각보다 쉽다.
쉽게 생각하기 위해 2차원에서 생각 후 3차원으로 확장해보자.
쉽게 생각하기 위해 이런 선분이 있다고 치자. 선분 $AB$는 (2,2) - (4,4)이고 $CD$는 (0,0) - (10,0)다.
먼저, 각 선분의 mid $p$는 (3,3), $q$는 (5,0)이다. $p$를 기준으로 left((2,2)방향)으로 이동하는 것보다 right((4,4))방향으로 이동하여 $q$와 이어주는게 더 작아짐은 그래프에서 쉽게 알 수 있다.
left방향이 더 작아지므로, 다시 $AB$를 (2,2) - (3,3)으로 생각하자.(divide)
다시 mid $p$를 (2.5,2.5)로 잡아보자. left로 이동하면 더 커지고, right로 이동해도 더 커진다.
즉, 여기가 현재 $q$를 기점으로 가장 작은 점이다. save하도록하자.
이제 $q$를 움직여보자.
위와 같은 방식으로 움직여보면,
최종적으로 $q$는 (2.5,0)에서 멈추게 된다.
위 과정을 다시 설명하면, 현재의 $q$기준으로 가장 가까운 $p$를 찾아가고, 다시 그 $p$를 기준으로 가장 가까운 $q$를 찾아간다.
그럼 위 과정을 반복해보자. 결과적으로, $q$기준으로 가장 가까운 $p$를 기준으로 가장 가까운 $q$를 기준으로 가장 가까운 $p$를 기준으로..... 반복이다.
이걸 돌리다 보면, 더 이상 $p, q$가 update가 되지 않게 될거고, 그 두 점의 거리가 shortest다.
자, 그럼 이걸 어떻게 구현을 할까?
첫 번째 걸림돌은 left로 이동할지 right로 이동할지 판단하는 것이다. 짧은 쪽으로만 divide해줘야하기 때문이다.
해결 방법은, 현재 mid를 기준으로 매우 작은 단위(이하 diff)만큼 이동시켜보고, 거기서 다른 점과 이었을 때, 감소하는 쪽으로 이동해야하는 것이다.
$p$가 (3,3)인 처음 상태에서 보면 (2.9999...,2.9999...)와 $q$를 이어보고, (3.0000...1,3.0000...1)와 $q$를 이어보고, 두 점 중 작은 점으로 이동하면 된다.
마냥 둘 중 작은 점으로 이동하면 되냐? 아니다.
이전에 언급했듯이, $p$가 이 상태에서 save된 이유는 left로 이동하던지 right로 이동하던지 똑같이 증가하기 때문이다.
즉, 현재 mid인 $p$와, $q$의 dist를 계산하고, left나 right의 dist중에 mid의 dist보다 작은 값이 있으면, 그 방향으로 이동 시켜준다. 의 로직으로 이어 나가면 현재 상태에서의 최소 dist를 구할 수 있다.
두 번째 걸림돌은, mid를 구하는 방식이다.
방금 설명한 recursive한 함수가 언제 멈추게 될까? left와 right중에 mid보다 작은 값이 없을 때만 멈추면 될까?
위 과정중에, left방향이 더 작아지므로, 다시 $AB$를 (2,2) - (3,3)으로 생각하자.(divide) 라고 언급한 부분이 있다.
mid - diff, mid + diff를 하여 left와 right를 구해주는데, divide를 계속 하다보니 범위가 너무 작아져서 mid - diff나 mid + diff가 divide해서 내려온 boundary를 넘는 경우, 더 이상 진행하면 안 하면 안 된다.(base case)
mid를 $(A + B) / 2$로 구하게 될 경우를 보자. 이 boundary체크가 까다롭다(라기보다는 귀찮다).
그러니, mid를 $A + c * B$로 구해보자. 여기서 $c$는 0과 1사이의 상수다. 이렇게 해줄경우 mid는 $A, B$사이의 점이라는 것이 자동으로 vailidation된다.
이렇게 해주기 위해선, 함수의 파라미터에 Point객체 자체를 넘겨주는 것이 아닌, double형 으로 $c$의 범위를 넘겨주고, 이 범위의 mid값으로 $c$를 할당해주면, 자등으로 mid의 coordinate가 구해진다.
