[11664] 선분과 점

---

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

11664번: 선분과 점

선분 AB와 점 C 사이의 거리의 최솟값을 구하는 문제이다.

 

처음에는 선분 AB를 지름으로 하는 원을 만들어서 최소 거리를 구해볼까 생각했는데, 3차원이라서 쉽지 않았다.

그래서 사용한 것이 삼분 탐색이다.

 

 

 

선분 AB 위에 놓여있는 점 x,y,z를 삼분탐색으로 계속 바꿔준다.

그렇게 갱신한 점이 점 C와 최소 거리를 갖는다! 하면 값을 바꿔주는 것이다.

 

 

근데 제일 애 먹었던게 탐색을 어떤 조건을 이용해 종료할 것인지이다.

start와 end의 값이 동일하면 종료시키려고 했는데, double형이다보니 소수점 10자리를 넘어가서 값이 미세하게 달라지는 경우가 있어 무한루프를 돌았다.

 

그래서 문제에 있는 조건을 이용하였다.

문제에 보면 허용 오차가 1e-06인 것을 볼 수 있다.

이것을 이용하여 start와 end 사이의 거리가 -10^-6, 10^6사이면(즉, 0에 가까워지면==start와 end의 값이 동일하면) 함수를 종료시켰다.

 

 

또한 탐색 이후 어떤 식으로 재귀를 구성할 것인지도 따져야 한다.

무턱대고 BinarySearch(start,key); BinarySearch(key,end); 하면 시간초과 뜬다.

그래서 아래 그림을 참고했다

start_C : start와 C 사이의 거리, end_C : end와 C 사이의 거리라고 치면, 

이렇게 그림을 그릴 수가 있고, 그럼 탐색하는 범위가 줄어들어 시간초과를 예방할 수 있다!

 

 

전체 코드는 아래와 같다.

#include <iostream>
#include <cmath>
using namespace std;

struct xyz { // xyz 구조체
	double x;
	double y;
	double z;
};

struct xyz A;
struct xyz B;
struct xyz C;

double minimum = 2147483647; // 초기 최솟값은 최대로 설정해야 ..

void BinarySearch(struct xyz start, struct xyz end) { 
	double temp = sqrt((start.x - end.x) * (start.x - end.x) + (start.y - end.y) * (start.y - end.y)
		+ (start.z - end.z) * (start.z - end.z)); // start와 end와의 거리를 구함
	double error = 1; 
	for (int i = 0; i < 6; i++) {
		error *= 0.1; // 오차는 10^-6까지 허용하므로
	}
	
	if (-1 * error <= temp && temp <= error) { // start와 end와의 거리가 허용오차 이내에서 0이면 같은 점을 가리킨다는 소리. 탐색 종료
		return;
	}

	struct xyz key; // 삼분탐색
	key.x = (start.x + end.x) / 2;;
	key.y = (start.y + end.y) / 2;
	key.z = (start.z + end.z) / 2;

	// len : 새로 설정한 선분AB 위의 점 key와 점 C사이의 거리
	double len = sqrt((key.x - C.x) * (key.x - C.x) + (key.y - C.y) * (key.y - C.y) + (key.z - C.z) * (key.z - C.z));
	
	minimum = (len < minimum) ? len : minimum; // 최솟값 갱신

	// start_C : start와 C 사이의 거리
	double start_C= sqrt((start.x - C.x) * (start.x - C.x) + (start.y - C.y) * (start.y - C.y) + (start.z - C.z) * (start.z - C.z));
	// end_C : end와 C 사이의 거리
	double end_C = sqrt((end.x - C.x) * (end.x - C.x) + (end.y - C.y) * (end.y - C.y) + (end.z - C.z) * (end.z - C.z));
	

	if (start_C > end_C) { // end_C와의 거리가 더 가깝다면 최소거리를 만족하는 점은 점 key와 점 end 사이에 있을것
		BinarySearch(key, end);
	}
	else { // 반대로는 start와 key 사이에 존재
		BinarySearch(start, key);
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> A.x >> A.y >> A.z;
	cin >> B.x >> B.y >> B.z;
	cin >> C.x >> C.y >> C.z;


	BinarySearch(A, B); // 선분 AB안에서 찾음
	 
	cout << fixed;
	cout.precision(10); // 소수점 10자리 출력
	cout << minimum;

}