Задание больше на математику, чем на программирование.... прошу помочь, ибо времени в обрез

Link
Короче данная программа на Руби работает так:
ввожу координаты одной точки (х и у), затем второй, третьей и т.д.
Программа рисует: при первой точке ничего, при второй — прямую, при третьей — треугольник, при чётвертой и далее — выпуклый n-угольник (оттого и название такое у проекта ) если точка лежит внутри уже нарисованной фигуры, то ничего не произойдёт... т.е. если был треугольник и я ввожу 4 точку, а она лежит в этом треугольнике, то ничего не произойдёт.... + программа считает периметр и площадь фигуры

Задание: Модифицируйте код так, чтобы индуктивно определить количество пар сторон выпуклой оболочки, расстояние между которыми не превосходит единицу.

Здравствуйте, Аноним, Вы писали:

А>Задание: Модифицируйте код так, чтобы индуктивно определить количество пар сторон выпуклой оболочки, расстояние между которыми не превосходит единицу.

Делать работу за тебя, думаю, найдется немного желающих, но если будут конкретные вопросы по алгоритмам — welcome ( сначала — полистай книжицу http://algolist.manual.ru/maths/geom/prsh/ )

Здравствуйте, FreshMeat, Вы писали:

FM>Здравствуйте, Аноним, Вы писали:

А>>Задание: Модифицируйте код так, чтобы индуктивно определить количество пар сторон выпуклой оболочки, расстояние между которыми не превосходит единицу.

FM>Делать работу за тебя, думаю, найдется немного желающих, но если будут конкретные вопросы по алгоритмам — welcome ( сначала — полистай книжицу http://algolist.manual.ru/maths/geom/prsh/ )

Это я уже читал... ход мыслей таков:

откуда имеем при 1 вершине 0 пар, при двух — 0, при трех — 3, при четырех и более надо определять расстояние
расстояние ищем следующим образом: любая сторона может находится левее, правее, или внахлыст
вот так
х_______х

х_______х

значит расстояние — либо минимум перпендикуляров, если они попадают на отрезок, либо расстояний между концами отрезка, если один левее или правее другого
и сразу говоришь что для n точек их n (количество соседних сторон), а остальное досчитываешь

просто я не знаю как это программно в данном проекте реализовать

Здравствуйте, Аноним, Вы писали:

А>значит расстояние — либо минимум перпендикуляров, если они попадают на отрезок, либо расстояний между концами отрезка, если один левее или правее другого
+1
А>и сразу говоришь что для n точек их n (количество соседних сторон), а остальное досчитываешь
n*n
А>просто я не знаю как это программно в данном проекте реализовать
я тоже

Здравствуйте, Аноним, Вы писали:

А>Задание: Модифицируйте код так, чтобы индуктивно определить количество пар сторон выпуклой оболочки, расстояние между которыми не превосходит единицу.

Алгоритм, требующий O(N) времени на каждую итерацию (соответственно, O(N^2) на все итерации) и O(N^2) дополнительной памяти.

Заведём множество искомых пар.
Каждый раз, добавляя вершину к оболочке, мы вычёркиваем от 1 до N-1 сторон и добавляем 2 стороны.
При этом
— вычеркнем из множества те пары, в которых упомянуты вычеркнутые стороны
— оббежим множество оставшихся сторон и померяем расстояния между ними и свежедобавленными
— добавим найденные пары в множество

Тупая реализация множества потребует O(log N) времени на каждую обслуженную пару, а умная (4-связный список) — O(1).

---

Алгоритм, не требующий дополнительной памяти, зато расходующий O(N^2) на каждую итерацию.
Запоминаем количество пар.
Удаляя сторону, оббегаем множество, считаем количество пар с этой стороной и декрементируем общее количество.
Добавляя сторону, снова оббегаем множество...

---

Подсчёт расстояния между двумя отрезками — отдельная и, в общем-то, несложная задача. Поиск по RSDN, алголисту и гуглю.

Ребят, дело в том, что алгоритм я примерно знаю, мне нужно реализовать енто дело в проекте я не знаю как в этот криво написанный проект (не я писал) вставить мою модификацию

Ни у кого не выходит? или никому не хочеться браться? :spy: