(не забыть бы)

[eddy_em]

Вот такую штуку подсказал аноним с ЛОРа для наискорейшего поиска выпуклой оболочки набора точек

Comments

[vlkamov]

Подозрительно напоминает сканирование :-)

[eddy_em]

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