Задача "Треугольник" Нахождения минимального периметра.

[iCaesy]

Задание:
На плоскости даны N точек. Никакие две точки не совпадают, никакие три не лежат на одной прямой. Найдите треугольник с вершинами в этих точках, имеющий наименьший возможный периметр.

Все это должно браться из файла, такого вида:
Input
5 - Кол-во точек
0 0 -т1
1.3 0 -т2
-2 0.1 -т3
1 0 -т4
10 10 - т5

В выходной файл выведите три числа – номера точек, которые должны быть вершинами треугольника, чтобы его периметр был минимален. Если решений несколько выведите любое из них.
Запись ответа в файл, такого вида:
Output
1 2 4

С этим проблем нет.

Интересуют несколько вопросов.
1.Как в паскале работать с переменной типа "точка", ведь она имеет два значения, допустим A(10,9); Запись в паскале будет вида A(x1,y1) ? Вводим х1 у1 и потом присваиваем переменной А ?

2.И на счет алгоритма. Как реализовать поиск этих трех точек при котором периметр будет минимальным.

Есть вариант:
Периметр - сумма всех сторон. То есть периметр будет минимальным при минимальных длинах 3х прямых. Нужно только найти 3 самых коротких прямых, которые образуют треугольник.

Формула нахождения длинны отрезка по двум точкам:
R:=sqrt ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

[Abstraction]

Нужно только найти 3 самых коротких прямых, которые образуют треугольник.

Да, нужно найти треугольник с минимальным периметром.
Соображение раз: если внутри треугольника есть точка, он не оптимален.
Соображение два: оптимальный треугольник с большей вероятностью включает короткие отрезки.
Соображение три: если сместить начало координат в некоторую точку, то из треугольников с вершиной в этой точке оптимальный можно найти, вначале беря точки вблизи.
Соображение четыре: с учётом неравенства max(|x|,|y|)<=sqrt(x*x+y*y)<=(|x|+| y|), можно отбрасывать варианты отрезков, заведомо превышающих по длине периметр оптимального треугольника.

[iCaesy]

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

[Abstraction]

"Каждый с каждым" - метод дохлый, требует O(N^3) операций.

Но если на некоторый момент мы уже нашли треугольник с периметром P, оптимальный треугольник заведомо не содержит рёбер длины от P/2.
Как черновая идея:
1) Выбрать следующую (вначале - первую) точку k как первую точку треугольника. Если точки кончились, перейти к 9).
2) Остальные точки отсортировать по максимуму модулей координатных разностей d во вспомогательный массив.
3) Взять i - следующую (вначале - первую) точку этого массива. Если точки кончились, перейти к 1).
4) Если уже найден треугольник с периметром 2d[i] и менее, перейти к 1).
5) Взять j - следующую (вначале - следующую непосредственно за i) точку вспомогательного массива. Если точки кончились, перейти к 3).
6) Если уже найден треугольник с периметром d[i]+d[j] и менее, перейти к 3).
7) Найти периметр p' треугольника (i,j,k); если у уже найденного треугольника периметр больше p' либо треугольников ещё не найдено, сделать (i,j,k) найденным треугольником.
8) Перейти к 5).
9) Найденный треугольник есть оптимальный треугольник.

[iCaesy]

Спасибо, попробую реализовать.

[Serge_Bliznykov]

"Каждый с каждым" - метод дохлый, требует O(N^3) операций.

если я правильно понимаю, то речь здесь идёт о сочетаниях (выбрать 3 из N):

Неупорядоченная выборка объёма k из множества, состоящего из n элементов (k ≤ n), называется сочетанием из k элементов по n.

количество вариантов подсчитывается по формуле:
это, конечно, тоже не фонтан в плане производительности, но при N=100, получается, например, 161700 вариантов, что почти на порядок меньше, чем N^3


это я к чему. При небольших N вполне допустимо решение с прямым перебором вершин. (при этом достаточно хранить номера точек и найденный минимальный периметр). Единственная оптимизация, если расстояние до очередной точки больше MinP/2 - то точку можно отбрасывать. Это немного сузит количество вариантов.

и ещё добавлю.
не уверен, что это оптимальное в плане производительности решение (точнее, это точно НЕ ОПТИМАЛЬНОЕ по производительности решение, это буквально "ТУПО В ЛОБ"!) но!
я бы брал 1-ю точку и искал две БЛИЖАЙШИЕ к ней точки.(перебор в цикле N-1 значений)
считал сумму расстояний как периметр.
брал вторую точку и перебор в цикле N-1 значений.
и так N раз (для каждой точки).
минимальное значение периметра найдено!

[Abstraction]

если я правильно понимаю, то речь здесь идёт о сочетаниях (выбрать 3 из N):

Извините меня, но сочетаний из N по 3 N(N-1)(N-2)/6=O(N^3), по определению O(x).

я бы брал 1-ю точку и искал две БЛИЖАЙШИЕ к ней точки.(перебор в цикле N-1 значений)
считал сумму расстояний как периметр.
брал вторую точку и перебор в цикле N-1 значений.
и так N раз (для каждой точки).

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

[Serge_Bliznykov]

Abstraction
мда... разгромили Вы мои выводы в пух и прах!

Сообщение от Abstraction

Извините меня, но сочетаний из N по 3 N(N-1)(N-2)/6=O(N^3), по определению O(x).

убедительно. полностью согласен.

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

и опять таки, вынужден согласиться!...

я написал программу, перебирает все возможные сочетания, ищет минимальное значение.

вот, может пригодится кому...

type Tpoint = record { тип Точка }
    x: double; { координата x }
    y: double; { координата y }
  end;

const N = 6;

const PArr : array[1..N] of TPoint =
  ((x:1;y:1),
   (x:2;y:2),
   (x:4;y:6),
   (x:4;y:7),
   (x:6;y:2),
   (x:7;y:1)
   );

function Distance(t1, t2 : integer) : extended;
begin
  Distance := sqrt( sqr(PArr[t1].x-PArr[t2].x) + sqr(PArr[t1].y-PArr[t2].y)  )
end;

var i1, i2, i3, k : integer;
  ab, bc, ac, per, minPer : extended;
  i1m, i2m, i3m : integer;
begin
  k := 0;
  i1m := -1;
  minPer := 1e10;
  for i1:=1 to N do
    for i2:=i1+1 to N do
      for i3:=i2+1 to N do
       if (i1<>i2) and (i2<>i3) and (i1<>i3) then begin
          ab := Distance(i1, i2);
          bc := Distance(i2, i3);
          ac := Distance(i1, i3);
          per := (ab+bc+ac);
          Writeln(i1, ' ', i2, ' ', i3,
                ' ab=',ab:7:3, ' bc=',bc:7:3, ' ac=',ac:7:3,
                ' perimeter = ', per:7:3);
          if per<minPer then begin
             minPer := per;
             i1m := i1; i2m := i2;  i3m := i3;
          end;
          inc(k)
       end;
  WriteLn('Сочетаний всего: ',k);
  WriteLn('Минимальный периметер = ',minPer:7:3,
       ' в точках ',
          i1m, ' ', i2m, ' ', i3m);
  Readln
end.

[iCaesy]

Спасибо огромное. Почти доделал по алгоритму Abstraction, позже выложу "свой" вариант.