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

Автор: irena 16.03.2005 16:17

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

Даны действительные числа x1, y1, x2, y2…xn, yn. Известно, что точки p1, p2…pn с координатами (x1, y1),(x2, y2)…(xn, yn) попарно различны. Найдите выпуклый многоугольник с вершинами некоторых из точек p1, p2…pn, который содержит все остальные точки. Многоугольник должен быть представлен последовательностью вершин.

Примечание. Две точки (x1, y1) и (x2, y2) не лежащие на прямой, определяемой уравнением ax+by+c=0, принадлежат одной полуплоскости, если ax1+by1+c и ax2+by2+c – числа одного знака. Уравнением прямой, проходящей через две различные точки (e, f) и (g, h), является уравнение (x-e)(h-f)-(y-f)(g-e)=0

Автор: virt 16.03.2005 16:31

http://algolist.manual.ru/maths/geom/convhull/

Автор: volvo 16.03.2005 16:36

virt
:yes:
или здесь: http://alglib.manual.ru/convex/convexshell.php

Автор: virt 16.03.2005 19:44

volvo:)
по первой ссылке алгоритмов больше ,на выбор.

Автор: irena 17.03.2005 4:36

А с кодом не поможите, желательно рекурсивным методом

Автор: volvo 17.03.2005 4:46

irena
Читайте здесь. (Только, пожалуйста, дочитайте до конца темы...)
http://forum.pascal.net.ru/index.php?showtopic=2874&view=findpost&p=27759

И в следующий раз пользуйтесь поиском...

Автор: irena 17.03.2005 14:10

Проблема в том, что задачу нужно решить с помощью рекурсии

Автор: volvo 17.03.2005 14:15

Что было написано в посте №5?

Теперь Вам

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

Автор: irena 17.03.2005 14:40

ага сложно, а вот для тебя наверно пустячок. Помоги а ?

Автор: volvo 17.03.2005 14:54

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