Здравствуйте mab, Вы писали:
fAX>>>Здравствуйте Sinclair, Вы писали:
fAX>>>>>Какие-то идеи? fAX>>>Дык надежда меня и питает ;-). fAX>>>А задача твоя, возможно и проще решается, т.к. convex hull (извини, по-русски не знаю) = O (N*LogN) + O(N^2) на нахождение наибольшего диаметра (можно, думается, и за N*LogN). S>>Упс! Сорри, очепятался — конечно N*N :) fAX>>>Hо всё же спасибо.
mab>convex hull всю жизнь по-русски называлось выпуклой оболочкой mab>Выражение O(N*LogN) + O(N^2) кажется как минимум странным, mab>поскольку оно есть просто O(N^2). O (N*LogN) — convex hull (eto ja znaju). A minimal`nyj diametr, kak ja i napisal, ochevidnym sposobom O(N^2), i pripisal "(можно, думается, и за N*LogN)". Takim obrazom "+" byl razdelitelem ;). V lubom sluchaet, mne prosto "ne ponravilos`" n^4, potomu i napisal. (Bol`she vsego mne ponravilos` N^N pri N=16000).
mab>Диаметр множества точек несложно ищется за O(N*log N), mab>если предварительно построить выпуклую оболочку алгоритмом mab>Грэхема.
Da, ja potom poiskal.
mab>Кстати говоря, алгоритм, который в этом треде был жестоко mab>обозван "алгоритмом Форда", по-настоящему называется mab>алгоритмом Флойда. Nadejus`, on ne obiditsja ;). U menja ochen` plohaja pamjat` na imena. Otchego chasto stradaju. :(
Sorry for translit.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
