Здравствуйте Sinclair, Вы писали:
S>Здравствуйте fAX, Вы писали:
fAX>>Здравствуйте Sinclair, Вы писали:
fAX>>>>Какие-то идеи?
fAX>>Дык надежда меня и питает .
fAX>>А задача твоя, возможно и проще решается, т.к. convex hull (извини, по-русски не знаю) = O (N*LogN) + O(N^2) на нахождение наибольшего диаметра (можно, думается, и за N*LogN).
S>Упс! Сорри, очепятался — конечно N*N
fAX>>Hо всё же спасибо.
convex hull всю жизнь по-русски называлось выпуклой оболочкой
Выражение O(N*LogN) + O(N^2) кажется как минимум странным,
поскольку оно есть просто O(N^2).
Диаметр множества точек несложно ищется за O(N*log N),
если предварительно построить выпуклую оболочку алгоритмом
Грэхема.
Кстати говоря, алгоритм, который в этом треде был жестоко
обозван "алгоритмом Форда", по-настоящему называется
алгоритмом Флойда.