https://www.acmicpc.net/problem/11662
시간 1초, 메모리 256MB
input :
- Ax, Ay, Bx, By, Cx, Cy, Dx, Dy(0 <= 좌표 <= 10000)
output :
- 가장 가까웠을 때의 거리를 출력한다. 절대/상대 오차는 10-6까지 허용
조건 :
- (x1, y1), (x2, y2)사이의 거리는
이다.
........... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
일단 거리를 구하는 식을 만들어서. 하던가///
삼분탐색을 하던가//// 하는데.....
삼분탐색을 통해 찾을 건 어차피 극값이다......
미분을 하겠다...
https://mslim8803.tistory.com/13
이 분의 풀이를 보면서 풀고 있었는데..
중간에 치환하고 미분하시는데 이해가 안 되더라 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
i에대해 미분하시는데 왜 i이지 거리고 있고....
그리고 치환이란 좋은 도구가 있는데 나는 치환안하고 미분 해보겠다고 막 하다가 대가리 터지고 나쵸만 먹음 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
암튼 결과는 미분을 통해 극값을 나타내는 i 혹은 (나는 t라고 보았다. 시간이니까) 을 구해서 거리를 계산한다.
이 떄 0으로 나누는 경우, 혹은 최솟값이 내가 상정한 범위 밖에 존재한다면/
이 함수의 거리 최솟값은 범위의 양 끝값 중 작은 값이 된다.
아직도 틀리긴 하는데;;; 이해라도 해ㅐ서 다행이다 쉽게 쉽게 치환해서 미분하자...
import sys
import math
data = list(map(int, sys.stdin.readline().split()))
def getDistance(x1, y1, x2, y2):
return math.sqrt( math.pow(x2 - x1, 2) + math.pow(y2 - y1, 2) )
aX1 = data[0]
aY1 = data[1]
aX2 = data[2]
aY2 = data[3]
cX1 = data[4]
cY1 = data[5]
cX2 = data[6]
cY2 = data[7]
interval = 1000000
aDX = (aX2 - aX1) / interval
aDY = (aY2 - aY1) / interval
cDX = (cX2 - cX1) / interval
cDY = (cY2 - cY1) / interval
try:
i = -1 * ( (aX1 - cX1) * (aDX - cDX) + (aY1 - cY1) * (aDY - cDY) ) / ( math.pow(aDX - cDX, 2) + math.pow(aDY - cDY, 2) )
ret = getDistance(aX1 + aDX * i, aY1 + aDY * i, cX1 + cDX * i, cY1 + cDY * i)
if 0 < i < interval:
print(ret)
else:
a = getDistance(aX1, aY1, cX1, cY1)
b = getDistance(aX2, aY2, cX2, cY2)
print(min(a, b))
except ZeroDivisionError:
a = getDistance(aX1, aY1, cX1, cY1)
b = getDistance(aX2, aY2, cX2, cY2)
print(min(a, b))
