Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Множество точек

Автор: Леха 12.11.2004 20:49

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

Автор: volvo 12.11.2004 20:51

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

Автор: Леха 12.11.2004 20:54

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

Автор: APAL 12.11.2004 21:02

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

Автор: APAL 12.11.2004 21:05

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

Автор: Леха 12.11.2004 21:07

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

Автор: APAL 12.11.2004 21:08

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

Автор: Леха 12.11.2004 21:15

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

Автор: APAL 12.11.2004 21:17

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

Автор: virt 12.11.2004 22:50

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

Автор: APAL 12.11.2004 23:06

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

Автор: Лита 13.11.2004 7:55

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

Автор: volvo 13.11.2004 8:49

Лита

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

Автор: Altair 13.11.2004 10:57

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

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

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

Автор: Лита 14.11.2004 9:26

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

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

Автор: trminator 14.11.2004 20:07

Код

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 15.11.2004 0:36

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


Угу! :yes:
Ура, терминатор вернулся!