чисто академическая задача по алгоритмам

← →
servs © (2003-10-28 14:47) [0]

Дали задачу в универе. Есть ломанная, заданная масивом координат вершин. Последняя точка == первой.
Нужно проверить есть самопересечения ломаной.

Задача вцелом примитивная, НО!!!
Обязательное требование
1. O(n), дин.
или
2. O(n*Log n) + доказать математически что O(n) нельзя.

O(n*Log n) знаю, можно сканированием сделать. Только реализация мутноватая получиться. + доказательство мутное, но можно.

А что делать с O(n)?

Заранее всем спасибо.

← →
pasha_golub © (2003-10-28 15:15) [1]

n - это кол-во точек?

Если Да, то рискну предложить проверку на выпуклость, хотя...

← →
servs © (2003-10-28 15:52) [2]

конечно :)

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

← →
XinSide © (2003-10-28 17:02) [3]

Пунктики распишите поподробнее plz, честно говоря не врубился в требования... А так мог бы помочь...

А что подробней?
1. Нужно либо найти алгоритм сложности О(н)
2. Или сложности О(н*лог(н)) + доказать за за время О(н) задача не решается.

То модератор. Не понимаю за что пост был перемещен. Раньше был раздел "Алгоритмы" - я бы туда написал, но его зачем то удалили.

ЗЫ. Я сам модератор в нескольких форумах, потому стараюсь всегда следовать правилам.

чисто академическая задача по алгоритмам Найти похожие ветки