Вниз
Скачать: CL | DM;

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

← →
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, честно говоря не врубился в требования... А так мог бы помочь...


← →
servs ©   (2003-10-29 13:00) [4]

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

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

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



Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.45 MB
Время: 0.019 c
7-66146
Zero Ice
2003-09-11 17:43
2003.11.20
Printers


8-66019
Бархатный
2003-07-24 17:39
2003.11.20
Наложить одну картинку на другую


14-66115
Иван Шихалев
2003-10-28 21:28
2003.11.20
Навеяло...


9-65685
The Kinslayer
2003-05-13 03:17
2003.11.20
О GLScene


1-65889
Oleg_
2003-11-08 00:12
2003.11.20
Jpeg в поток




   Наверх