5032 : 점과 선분 사이의 거리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
점 $A$와 선분 $BC$ 사이의 최단 거리를 구하는 문제입니다.
직선과의 거리는 항상 수선의 발까지의 거리이지만, 이 문제는 양 끝이 정해진 '선분' $BC$와의 거리이므로,
점 $A$에서 내린 수선의 발 $H$가 선분 위에 떨어지는지, 아니면 선분 밖으로 벗어나는지에 따라 3가지 경우(패턴)로 나뉩니다.
1️⃣ 수선의 발 위치 판별하기 : 벡터의 내적 (Dot Product)
두 벡터의 내적은 사잇각 $\theta$의 코사인 부호에 의해 결정됩니다 ($\vec{u} \cdot \vec{v} = |\vec{u}||\vec{v}|\cos\theta$).
• $\theta > 90^\circ$ (둔각) $\iff$ 내적 $< 0$
• $\theta \le 90^\circ$ (예각 또는 직각) $\iff$ 내적 $\ge 0$
2️⃣ 선분 내부일 때 최단거리 구하기 : 2차원 외적 (Cross Product)
Pattern 2에서 수선의 길이 $d$를 구할 때, 복잡한 직선의 방정식을 세울 필요가 없습니다.
두 벡터 $\vec{BA}, \vec{BC}$가 이루는 평행사변형의 넓이를 2차원 외적으로 구한 뒤, 밑변 길이 $|\vec{BC}|$로 나누면 높이 $d$가 단 한 번에 나옵니다!
💡 한눈에 정리하는 구현 흐름 (알고리즘 요약):
1. 기준 벡터 계산: $\vec{BA} = (a_x - b_x, a_y - b_y)$, $\vec{BC} = (c_x - b_x, c_y - b_y)$, $\vec{CA} = (a_x - c_x, a_y - c_y)$, $\vec{CB} = (b_x - c_x, b_y - c_y)$
2. 점 $B$에서 둔각 여부: $\vec{BA} \cdot \vec{BC} < 0$ 이면 $\implies$ 정답 $= \sqrt{BA_x^2 + BA_y^2}$
3. 점 $C$에서 둔각 여부: $\vec{CA} \cdot \vec{CB} < 0$ 이면 $\implies$ 정답 $= \sqrt{CA_x^2 + CA_y^2}$
4. 그 외(선분 내부): 외적으로 구한 높이 $\implies$ 정답 $= \frac{|BA_x \cdot BC_y - BA_y \cdot BC_x|}{\sqrt{BC_x^2 + BC_y^2}}$
1. 기준 벡터 계산: $\vec{BA} = (a_x - b_x, a_y - b_y)$, $\vec{BC} = (c_x - b_x, c_y - b_y)$, $\vec{CA} = (a_x - c_x, a_y - c_y)$, $\vec{CB} = (b_x - c_x, b_y - c_y)$
2. 점 $B$에서 둔각 여부: $\vec{BA} \cdot \vec{BC} < 0$ 이면 $\implies$ 정답 $= \sqrt{BA_x^2 + BA_y^2}$
3. 점 $C$에서 둔각 여부: $\vec{CA} \cdot \vec{CB} < 0$ 이면 $\implies$ 정답 $= \sqrt{CA_x^2 + CA_y^2}$
4. 그 외(선분 내부): 외적으로 구한 높이 $\implies$ 정답 $= \frac{|BA_x \cdot BC_y - BA_y \cdot BC_x|}{\sqrt{BC_x^2 + BC_y^2}}$
입력 설명
세 점의 좌표가 주어집니다.
출력 설명
거리를 출력하십시오.
정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하라면 정답으로 인정합니다.
(단, 출력값을 $A$, 실제 정답을 $B$라 할 때 절대 오차는 $|A - B|$, 상대 오차는 $\frac{|A - B|}{|B|}$로 정의합니다.)
정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하라면 정답으로 인정합니다.
(단, 출력값을 $A$, 실제 정답을 $B$라 할 때 절대 오차는 $|A - B|$, 상대 오차는 $\frac{|A - B|}{|B|}$로 정의합니다.)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
0 0
0 5
5 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3.5355339059327378