일부 주택이 위치한 좌표점 목록을 포함하는 위치 목록이 있다고 가정합니다. 임의의 지점에서 (xc, yc)까지의 유클리드 거리의 합이 최소가 되도록 (xc, yc)에 서비스 센터를 만들고자 하는 경우. 따라서 최소 거리의 합을 구해야 합니다.
따라서 입력이 위치 =[(10,11),(11,10),(11,12),(12,11)]과 같으면 출력은 4.0
이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
numIter :=50
-
total() 함수를 정의합니다. cx, cy, 위치가 필요합니다.
-
총계 :=0.0
-
위치의 각 p에 대해 수행
-
x, y :=p
-
total :=total + (cx, cy)와 (x, y) 사이의 유클리드 거리
-
-
총 반환
-
함수 fy() 를 정의합니다. x, 위치가 필요합니다.
-
l :=0, r :=101
-
해상도 :=0
-
범위 0에서 numIter까지의 i에 대해
-
y1 :=l + (r - l) / 3
-
y2 :=r - (r - l) / 3
-
t1 :=합계(x, y1, 위치)
-
t2 :=합계(x, y2, 위치)
-
res :=t1과 t2의 최소값
-
t1
-
r :=y2
-
-
그렇지 않으면
-
내가 :=y1
-
-
반환 해상도
-
함수 fx() 를 정의합니다. 이것은 위치를 차지할 것입니다
-
l :=0, r :=101
-
해상도 :=0
-
범위 0에서 numIter까지의 i에 대해
-
x1 :=l + (r - l) / 3
-
x2 :=r - (r - l) / 3
-
t1 :=fy(x1, 위치)
-
t2 :=fy(x2, 위치)
-
res :=t1과 t2의 최소값
-
t1
-
r :=x2
-
-
그렇지 않으면
-
내가 :=x1
-
-
-
반환 해상도
-
기본 메서드에서 fx(positions)
를 반환합니다.예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
from math import sqrt
def solve(points):
numIter = 50
def total(cx, cy, positions):
total = 0.0
for p in positions:
x, y = p
total += sqrt((cx - x) * (cx - x) + (cy - y) * (cy - y))
return total
def fy(x, positions):
l, r = 0, 101
res = 0
for i in range(numIter):
y1 = l + (r - l) / 3
y2 = r - (r - l) / 3
t1 = total(x, y1, positions)
t2 = total(x, y2, positions)
res = min(t1, t2)
if t1 < t2:
r = y2
else:
l = y1
return res
def fx(positions):
l, r = 0, 101
res = 0
for i in range(numIter):
x1 = l + (r - l) / 3
x2 = r - (r - l) / 3
t1 = fy(x1, positions)
t2 = fy(x2, positions)
res = min(t1, t2)
if t1 < t2:
r = x2
else:
l = x1
return res
return fx(positions)
positions = [(10,11),(11,10),(11,12),(12,11)]
print(solve(positions)) 입력
[(10,11),(11,10),(11,12),(12,11)]
출력
4.0