Определение периметра четырехугольника

[strateg66]

Здравствуйте.
Мне не нужно решение задачи, скорее нужна помощь по алгоритму решения.
Необходимо найти периметр четырехугольника с заданными координатами вершин. все кажется довольно таки просто, кроме того, что стороны четырехугольника неизвестны.
Для первого случая (рис.1) все работает, а вот на рис 2 простой алгоритм перестает работать.

[eoln]

1) Берём 2 точки (назовём эти точки А и Б) которые максимально удалены (длину отрезка через координаты надеюсь знаете как найти) - это даст нам уверенность что мы выбрали диагональ. Оставшиеся точки назовём В и Г
2) Вычисляем площади треугольников АБВ и АБГ (через координаты по формуле Герона)
3) Складываем и получаем ответ

[IT-man]

2eoln а периметр то тут причем?

[eoln]

Сообщение от IT-man

2eoln а периметр то тут причем?

Да уж, чего-то я попутал (мне показалось там площадь), чуть изменим 2 пункт
2) Вычисляем длины сторон АВ, АГ, БВ, БГ
3) Складываем и получаем ответ

[ОДИНОЧЕСТВО В СЕТИ]

Берём 2 точки (назовём эти точки А и Б) которые максимально удалены (длину отрезка через координаты надеюсь знаете как найти) - это даст нам уверенность что мы выбрали диагональ.

Не факт! Пример трапеция!

[Serge_Bliznykov]

Одиночество, Вы, как обычно, абсолютно правы.
Но уже выяснили, вычисление площади в данном случае не нужно...

2) Вычисляем длины сторон АВ, АГ, БВ, БГ

добавлю, что расстояние между двумя любыми точками, заданными своими координами, находится как квадратный корень из суммы квадратов разностей координат:
пусть координаты точки A (x1, y1) и точки B (x2, y2 )
тогда расстояние AB =

  Sab = SQRT( SQR(x2-x1) + SQR(y2-y1))

[cherw9!40k]

Это из теории графов. Погугли - есть алгоритмы определения замкнутого пути с отсутствием пересечений.

[strateg66]

Во-первых у меня на рисунке нет вершин А, В, Г, Б, а есть вершины A, B, C, D.
Во-вторых, как правильно меня понял червячок, основная проблема - нахождение именно правильных сторон. Ведь в двух предоставленных вариантах стороны у четырехугольника - разные. В первом: AB, BC, CD, DA, во-втором: AD, DB, BC, CA. Отсюда, собственно, и затруднение в нахождении алгоритма.
К сожалению, ничего путного по теории графов пока найти не могу.

[cherw9!40k]

Предлагаю алгоритм поиска в длину (упрощенный, ибо количество вершин статично) с использованием проверки, есть ли пересечение при найденном обходе (ввиду того, что известны координаты и кол-во вершин 4, опять таки проверить не составит труда).

[cherw9!40k]

Тут еще такая идея возникла. Точки расположены на координатной прямой. Берешь плоскость (можно не брать, можно только представлять в уме )) ). Проверяешь по Х какие точки расположены правее, какие левее. Потом, аналогично по Y - кто выше, кто ниже. Ну, и там как-нибудь сообразить.