Множество точек, Найти макс. растояние Опции

[Леха]

Привет всем кто мне поможет. Дана задача
Во множестве точек на плоскости найти пару точек с максимальным расстоянием между ними.

[volvo]

А в чем проблема? знаешь, как находится расстояние между двумя точками? а потом - полным перебором и искать максимальное из расстояний ...

Сообщение отредактировано: volvo - 12.11.2004 16:52

[Леха]

Вот в этом и проблема как можно найти расстояние, а затем среди них выбрать максимальное.

[APAL]

Расстояние - по формуле.
Максимальное - полным перебором.

[APAL]

Теорема пифагора: квадрат гипотенузы = сумме квдратов катетов.

[Леха]

А по подробнее. По какой формуле? Каким перебором? Ну допутим с перебором я справлюсь, но для этого мне нужно найти расстояния.

[APAL]

См. мое предидущее сообщение. Катеты - это как раз и есть X и Y точки.
Вернее: (X1-X2)^2+(Y1-Y2)^2=(расстояние между точками)^2

[Леха]

А не можешь написать как это будет выглядеть в Паскале?

[APAL]

А самому подумать?

[virt]

как вариант построить выпуклую оболочку ,и потом перебором только по точкам принадлежащим этой оболочке.

[APAL]

virt
Зачем нам выпуклая оболочка? Все точки на плоскости.
Я уже и формулу привел...

[Лита]

APAL
а при чем здесь теорема Пифагора для прямоугольного треугольника, если надо найти расстояния между ДВУМЯ точками?
мошь я че не понимаю...

[volvo]

Лита

Проекция отрезка на ось абсцисс - один катет, проекция на ось ординат - второй. По теореме Пифагора находим гипотенузу = расстояние между точками ... :yes:

[Altair]

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

а при чем здесь теорема Пифагора

А если я скажу, что нажо определить длинну вектора от одной точки до другой, будет понятнее

[Лита]

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

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

[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:
Ура, терминатор вернулся!