Developing.ru

Есть несложная задача для мастеров..наверное минут на 20, не больше.(кто хочет, может засечь для интереса )
Но очень надо ее решить за 1.5 дня!!А я сам написать не могу, так как не программист..
Итак, есть множество точек на плоскости(задано массивом n на 2 - координаты точек). Надо найти многоугольник, не обязательно выпуклый, чтобы его периметр был максимален. (естественно, многоугольник без самопересечения)
Пожалуйста!..жить хочется

все N точек должны быть задействованы?

а разве есть вариант, когда задействованы не все точки и периметр максимален?
по моим соображениям такого варианта вроде нет..периметр все-таки..

сейчас неожиданно сообразил, что не всегда надо выбирать максимально удаленную вершину и проверять на самопересечение...есть пример, когда выгоднее не брать самую удаленную...так что, может быть, и не все врешины надо использовать..но желательно!

хотя если с циклом по всем вершинам как возможным начальным, то такой проблемы нет..хотя как проверять на самопересечение отрезок и многоугольник

да, точно не обязательно все вершины..

Тогда рекурсивным перебором. Всего переборов (Сумма по i от 1 до N) С(i,N). Т. е. уже для 10 точек - 6235301 вариантов, для 15 - 2246953104076, для 20 - 4180411311071440001. Считайте

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