Помощь - Поиск - Пользователи - Календарь
Полная версия: Множество точек
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Леха
Привет всем кто мне поможет. Дана задача
Во множестве точек на плоскости найти пару точек с максимальным расстоянием между ними.
volvo
А в чем проблема? знаешь, как находится расстояние между двумя точками? а потом - полным перебором и искать максимальное из расстояний ...
Леха
Вот в этом и проблема как можно найти расстояние, а затем среди них выбрать максимальное.
APAL
Расстояние - по формуле.
Максимальное - полным перебором.
APAL
Теорема пифагора: квадрат гипотенузы = сумме квдратов катетов.
Леха
А по подробнее. По какой формуле? Каким перебором? Ну допутим с перебором я справлюсь, но для этого мне нужно найти расстояния.
APAL
См. мое предидущее сообщение. Катеты - это как раз и есть X и Y точки.
Вернее: (X1-X2)^2+(Y1-Y2)^2=(расстояние между точками)^2
Леха
А не можешь написать как это будет выглядеть в Паскале?
APAL
А самому подумать?
virt
как вариант построить выпуклую оболочку ,и потом перебором только по точкам принадлежащим этой оболочке.
APAL
virt
Зачем нам выпуклая оболочка? Все точки на плоскости.
Я уже и формулу привел...
Лита
APAL
а при чем здесь теорема Пифагора для прямоугольного треугольника, если надо найти расстояния между ДВУМЯ точками? blink.gif
мошь я че не понимаю... huh.gif
volvo
Лита

Проекция отрезка на ось абсцисс - один катет, проекция на ось ординат - второй. По теореме Пифагора находим гипотенузу = расстояние между точками ... :yes:
Altair
Общий алгоритм таков:
1. взять произвольную точку.
2. Вычислить расстояние от нее до всех других (циклически).
3. выбрать максимальное.
Цитата
а при чем здесь теорема Пифагора

А если я скажу, что нажо определить длинну вектора от одной точки до другой, будет понятнее smile.gif
Лита
Цитата(Oleg_Z @ 13.11.04 6:57)
Общий алгоритм таков:
1. взять произвольную точку.
2. Вычислить расстояние от нее до всех других (циклически).
3. выбрать максимальное.

так это для каждой точки надо делать такое, правильно??? huh.gif
trminator
Код

const maxn = 100;
var i, j : integer;
   x, y : array[1..maxn] of double; // Координаты точек
   n : integer;
   max_ro : double;
   max_point1, max_point2  : integer; // номер точки

function ro(i, j : integer) : double;
{Тут работает теорема им. тов. Пифагора}
begin
   ro := sqr(x[i] - x[j]) + sqr(y[i] - y[j]);
   // На квадрат забиваем. (r1^2 > r2^2) <=> ((r1 > r2) & (r1>=0, r2>=0))
end;

begin
   Write('Введи количество точек > '); readLn(n);
   for i := 1 to n do
   begin
       write('Координаты ', i, '-й точки > '); readLn(x[i], y[i]);
   end;
   max_ro := 0;

{Проверяем все точки. Перебор}
   for i := 1 to n do
       for j := i to n do // от i, так как если проверили расстояние 1-2, то 2-1 уже не надо =)
       if ro(i, j) > max_ro then
       begin
           max_ro := ro(i, j);
           max_point1 := i; max_point2 := j;
       end;
   writeLn('Точки с координатами (', x[max_point1]:0:3, y[max_point1]:0:3,
           ') и (',x[max_point2]:0:3, y[max_point2]:0:3,')');
end.
Altair
Цитата
так это для каждой точки надо делать такое, правильно??? 


Угу! :yes:
Ура, терминатор вернулся!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.