선분과 점 (백준 Gold5)

문제

3차원 좌표 평면 위에 선분 하나와 점 하나가 있다. 선분의 양 끝점은 A(Ax, Ay, Az)와 B(Bx, By, Bz)로 나타낼 수 있다. 점의 좌표는 C(Cx, Cy, Cz) 이다. 선분과 점 사이의 거리의 최솟값을 구하는 프로그램을 작성하시오.

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

 

풀이

이번에는 구조체와 삼분 탐색을 활용한 풀이법을 잘 확인할 수 있는 문제를 들고 와보았다.

이중 pair나 tuple로도 구조체를 대체할 수 있지만, 일단 가독성이 좋고 확장성과 안정성이 뛰어나 구조체를 활용했다.

 

물론 나 또한 평소에 구조체를 더 많이 사용하는 듯...

 

C++ 풀이)

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

// 삼분 탐색
struct Pos {
	double x, y, z;
};

Pos A, B, C;

double Distance(double x1, double y1, double z1, double x2, double y2, double z2) {
	return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2) + pow(z2 - z1, 2));
}

int main() {
	cin >> A.x >> A.y >> A.z >> B.x >> B.y >> B.z >> C.x >> C.y >> C.z;

	double low = 0, high = 1;
	while (high - low > 0.0000001) {
		double ref1 = (2 * low + high) / 3;
        double ref2 = (low + 2 * high) / 3;
        
        Pos Mid1, Mid2;

		Mid1.x = B.x * ref1 + A.x * (1 - ref1), Mid2.x = B.x * ref2 + A.x * (1 - ref2);
		Mid1.y = B.y * ref1 + A.y * (1 - ref1), Mid2.y = B.y * ref2 + A.y * (1 - ref2);
		Mid1.z = B.z * ref1 + A.z * (1 - ref1), Mid2.z = B.z * ref2 + A.z * (1 - ref2);

		double dist1 = Distance(C.x, C.y, C.z, Mid1.x, Mid1.y, Mid1.z);
		double dist2 = Distance(C.x, C.y, C.z, Mid2.x, Mid2.y, Mid2.z);

		if (dist1 > dist2)
			low = ref1;
		else
			high = ref2;
	}

	Pos Ans;
	Ans.x = B.x * low + A.x * (1 - low);
	Ans.y = B.y * low + A.y * (1 - low);
	Ans.z = B.z * low + A.z * (1 - low);

	cout << fixed; cout.precision(20);
	cout << Distance(Ans.x, Ans.y, Ans.z, C.x, C.y, C.z) << '\n';

	return 0;
}