Задача 16.
На двумерной плоскости задано N точек с координатами (X1,Y1), (X2,Y2), ..., (Xn,Yn). Написать программу, которая находит такую точку Z(x,y), сумма расстояний от которой до остальных минимальна и:
а) Z - одна из заданных точек;
b) Z - произвольная точка плоскости.
|
Решение задачи 16.
А) Единственный способ найти такую точку - это вычислить все суммы расстояний, а затем взять среди них минимальную. Расстояние между точками x(x1,x2) и y(y1,y2) считается по формуле
.
Если же расстояние считается по формуле
d(x,y)=|x1-y1|+|x2-y2|,
то в этом случае применима идея решения задачи 15 (посмотрите, что и как тогда получается).
В) Z есть центр масс системы из N точек
Zx=(x1+ ... +xN)/N
Zy=(y1+ ... +yN)/N
|
