Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Центр помощи > [Pasсal] Двумерный массив

Автор: Mitya 9.3.2007, 16:18

Массив KOORD[1..2,1..n] представляет собой координаты N точек на плоскости: 1-я строка - абсциссы, 2-я строка - ординаты. Найти номера двух точек, расстояние между которыми максимально.

X 1 3 4 2 4
Y 2 3 5 4 1

В данном случае N=5

Всем огромное спасибо!

Автор: Strannik 9.3.2007, 19:57

Алгоритм тупой (O(N^2)) или умный (O(NlogN)) нужен?

Автор: Mitya 9.3.2007, 21:25

Цитата(Strannik @ 9.3.2007, 19:57

)

Алгоритм тупой (O(N^2)) или умный (O(NlogN)) нужен?

А циклом for нельзя? Просто я еще учусь, а такого даже не знаю... там я написал for i:=1 to 2 do for j:=1 to n do begin А вот дальше - ступор...

Автор: Kuvaldis 9.3.2007, 21:57

Код


const
    MAX = 100;

type
  Point = record
      x, y : integer;
  end;

var
    list : array [1..MAX] of Point;
    n, i, k : integer;
    max_len : real;
    curr_len : real;
    pos1, pos2 : integer;

// функция расстояния между точками    
function PointLen(a, b : Point) : real;
begin
      PointLen := sqrt( sqr(a.x - b.x) + sqr(a.y - b.y) );
end;

begin
    writeln('Input points count');
    readln(n);
    writeln('Input points');
    for i := 1 to n do
    begin
        writeln(i, ' point coordinates (x, y)');
        read( list[i].x );
        read( list[i].y );
    end;

    pos1 := 1;                       // начальная инициализация
    pos2 := 2;
    max_len := PointLen(list[1], list[2]);

    // основные циклы поиска
    for i := 1 to n - 1 do begin
        for k := i + 1 to n do  begin
            curr_len := PointLen( list[i], list[k] );
            if (curr_len > max_len) then begin
               max_len := curr_len;
               pos1 := i;
               pos2 := k;
            end;
        end;
    end;

    writeln('MaxLen = ', max_len : 0 : 2);
    writeln('Positions: ', pos1 : 4, pos2 : 4);
    readln;
    readln;
end.

Автор: FireSnake 9.3.2007, 22:43

Эт ж что за умный сложностью NlogN? Поделиси соображениями.

Автор: Strannik 10.3.2007, 12:09

RTFM(кормен).
А если честно - я его сам не знаю... Но в кормене в разделе "Вычислительная геометрия" он точно есть.

Автор: MBo 10.3.2007, 12:39

Для нахождения пары с максимальным расстоянием за NLogN можно построить выпуклую оболочку (Convex Hull, есть метод с асимптотикой O(Nh), где h - число точек в оболочке, на практике методы обычно близки по скорости, если распределение точек не специально хитрое), наиболее удаленные точки будут ей принадлежать

Кроме того, есть методы с делением облака точек на клетки. Если клеток достаточно много, то достаточно проверять расстояния до небольшого количества дальних клеток

Автор: Strannik 10.3.2007, 13:42

Цитата

наиболее удаленные точки будут ей принадлежать

А если все точки входят в выпуклую оболочку? Если я правильно понял - тогда всё равно квадрат выйдет...
В кормене алгоритм типа "разделяй и властвуй"... надо будет разобратся...

Автор: FireSnake 10.3.2007, 21:40

Странник прав, оболочка строится за квадрат.

Цитата

RTFM(кормен)

Кормен это точно FM:)

Автор: MBo 10.3.2007, 23:09

Strannik,
>А если все точки входят в выпуклую оболочку? Если я правильно понял - тогда всё равно квадрат выйдет...

Выпуклая оболочка строится за O(NLogN), например, по Грэхему. Асимптотика в его методе не зависит от количества точек в оболочке, а обусловлена сортировкой
Расстояние между наиболее удаленными точками на ней находится за линейное время (Rotating Calipers)

FireSnake,
>оболочка строится за квадрат.
Можно и за экспоненциальное время, но незачем, если есть методы с гарантированным NLogN

Автор: Strannik 12.3.2007, 14:44

Цитата

Выпуклая оболочка строится за O(NLogN)

Это так, я не то имел ввиду...

Цитата

Расстояние между наиболее удаленными точками на ней находится за линейное время (Rotating Calipers)

Об этом по подробнее можно?

Добавлено @ 14:48

Цитата

тогда всё равно квадрат выйдет

Я имел ввиду поиск двух наиболее удалённых...

Автор: MBo 12.3.2007, 15:31

>Об этом по подробнее можно?
гуглом много находится. Вот одна из первых ссылок
http://cgm.cs.mcgill.ca/~orm/rotcal.frame.html

Автор: Mitya 14.3.2007, 15:23

Огромное спасибо всем, кто помог и помогает людям!!! Низкий всем Вам поклон!