A,B를 끝점으로 하는 선분에서 C까지 거리의 최소값을 구하는 문제다.
C에서 L(A,B)(=A,B를 통과하는 직선) 로 내린 수선의 발을 D라 하자.
여기서는 경우의 수가 2가지 있다.
1. 수선의 발 D가 A,B 사이에 있는 경우.
2. 아닌 경우.
여기서 수선의 발 D가 A,B 사이에 있는지 확인하는 방법으로 내적을 사용한다.
AB를 각각 AC, BC에 내적시킨 값을 a,b라고 하자.
이 결과를 곱한 값인 a*b < 0, 즉 음수면 수선의 발은 AB사이에 있고 a*b == 0이면 수선의 발이 A혹은 B이다.
a*b<=0 이면 선분까지의 최단거리를 구해서 출력하면 되고 아닌 경우에는 dist(A,C), dist(B,C) 둘 중 작은 값을 출력하면 된다.
<코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <stdio.h> #include <algorithm> using namespace std; typedef double db; struct pt { db x, y, z; pt(db x = 0, db y = 0, db z = 0) : x(x),y(y),z(z) {} pt operator-(const pt &a) { return pt(x - a.x, y - a.y, z - a.z); } //외적 pt operator*(const pt &a) { return pt(y*a.z - z*a.y, z*a.x - x*a.z, x*a.y - y*a.x); } //내적 db operator|(const pt &a) { return x*a.x + y*a.y + z*a.z; } }; //벡터 길이 db mul(pt a) { return sqrt(a | a); } int main() { pt a[3]; for (int i = 0; i < 3; i++) scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].z); pt b = a[1] - a[0], c = a[2] - a[0], d = a[2] - a[1]; //최단거리는 외적을 이용한다. if ((b|c)*(b|d) <= 0) printf("%.10lf\n", mul(b*c) / mul(b)); else printf("%.10lf\n", min(mul(c), mul(d))); return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 10025 게으른 백곰 (0) | 2017.08.30 |
|---|---|
| 14619 섬 여행 (0) | 2017.08.30 |
| 1069 집으로 (0) | 2017.08.30 |
| 2570 비숍 (0) | 2017.08.30 |
| 2316 도시 왕복하기 (0) | 2017.08.30 |