Привет всем кто мне поможет. Дана задача
Во множестве точек на плоскости найти пару точек с максимальным расстоянием между ними.
А в чем проблема? знаешь, как находится расстояние между двумя точками? а потом - полным перебором и искать максимальное из расстояний ...
Вот в этом и проблема как можно найти расстояние, а затем среди них выбрать максимальное.
Расстояние - по формуле.
Максимальное - полным перебором.
Теорема пифагора: квадрат гипотенузы = сумме квдратов катетов.
А по подробнее. По какой формуле? Каким перебором? Ну допутим с перебором я справлюсь, но для этого мне нужно найти расстояния.
См. мое предидущее сообщение. Катеты - это как раз и есть X и Y точки.
Вернее: (X1-X2)^2+(Y1-Y2)^2=(расстояние между точками)^2
А не можешь написать как это будет выглядеть в Паскале?
А самому подумать?
как вариант построить выпуклую оболочку ,и потом перебором только по точкам принадлежащим этой оболочке.
virt
Зачем нам выпуклая оболочка? Все точки на плоскости.
Я уже и формулу привел...
APAL
а при чем здесь теорема Пифагора для прямоугольного треугольника, если надо найти расстояния между ДВУМЯ точками?
мошь я че не понимаю...
Лита
Проекция отрезка на ось абсцисс - один катет, проекция на ось ординат - второй. По теореме Пифагора находим гипотенузу = расстояние между точками ... :yes:
Общий алгоритм таков:
1. взять произвольную точку.
2. Вычислить расстояние от нее до всех других (циклически).
3. выбрать максимальное.