Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Геометрия >> Номер 16

[Назад]    [Содержание ]    [Вперед]

  


Номер 16


  Условие: Номер 16


Задача 16. На двумерной плоскости задано N точек с координатами (X1,Y1), (X2,Y2), ..., (Xn,Yn). Написать программу, которая находит такую точку Z(x,y), сумма расстояний от которой до остальных минимальна и: а) Z - одна из заданных точек; b) Z - произвольная точка плоскости.

  Решение задачи: Номер 16


Решение задачи 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

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017