백준 11662번 - 민호와 강호
출처 : 11662번: 민호와 강호 (acmicpc.net)
11662번: 민호와 강호
민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다. 민호와 강호는 동시에 출발하고, 민
www.acmicpc.net
민호와 강호 성공 스페셜
시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율
| 1 초 | 256 MB | 750 | 328 | 221 | 42.996% |
문제
민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다. 민호와 강호는 동시에 출발하고, 민호가 점 B에 도착하는 순간 강호도 점 D에 도착한다. 또, 두 사람은 항상 일정한 속도로 걸어간다. 두 사람의 거리가 가장 가까울 때, 거리를 구하는 프로그램을 작성하시오.
두 점 (x1, y1), (x2, y2) 사이의 거리는 (x2−x1)2+(y2−y1)2 이다.
입력
첫째 줄에 Ax, Ay, Bx, By, Cx, Cy, Dx, Dy가 주어진다. 입력으로 주어지는 모든 좌표는 0보다 크거나 같고, 10000보다 작거나 같은 정수이다.
출력
민호와 강호가 가장 가까웠을 때의 거리를 출력한다. 절대/상대 오차는 10-6까지 허용한다.
예제 입력 1 복사
0 0 1 1 2 2 3 3
예제 출력 1 복사
2.8284271247
예제 입력 2 복사
0 0 1 1 1 0 0 1
예제 출력 2 복사
0.0000000000
예제 입력 3 복사
0 0 10 20 30 0 5 10
예제 출력 3 복사
8.2416338387
예제 입력 4 복사
5 5 10 10 7 2 20 30
예제 출력 4 복사
2.8745554697
[ 문제 설명 ]
이 문제는 두 점이 직선 운동을 할 때 두 직선 간의 거리를 좌표로 두면 어떤 모양을 둘 것이고 그 모양에서 가장 작은 값이 우리가 원하는 최솟값이 될 거라는 intuition이 있어야 이 문제를 이해할 수 있다.
그림으로 설명하겠다.
[ 코드 ]
def threeSearch(left, right):
while abs(right - left) > 1e-9:
left3 = (2 * left + right) / 3
right3 = (left + 2 * right) / 3
if dist(left3) > dist(right3):
left = left3
else:
right = right3
return dist(left)
def dist(t):
mx = ax * t + bx * (1 - t)
my = ay * t + by * (1 - t)
kx = cx * t + dx * (1 - t)
ky = cy * t + dy * (1 - t)
return ((kx - mx) ** 2 + (ky - my) ** 2) ** 0.5
ax, ay, bx, by, cx, cy, dx, dy = map(int, input().split())
print("%.16f" % threeSearch(0, 1)) # 비율을 1을 기준으로 했으므로후기
약간 수학적인 사고가 필요하고, 지식이 필요한 문제
개인적으로 이런 문제를 풀면 기분은 좋지만 이런 문제는
과연 컴공의 코딩력과 관련이 있을까?라는 의문은 조금 든다.