Для справки: задача важная, нужная и популярная, и решений у неё есть много. Одно из решений приведено в книге «Алгоритмы: построение и анализ» Т. Кормена, являющейся университетским учебником для большинства вузов, начиная с MIT. Но в девяностых на окраине России про Кормена ещё не знали, и пришлось выкручиваться своими силами.
Насколько я понимаю, от нас ожидалось что-то вроде алгоритма Грэхема: взять самую левую точку, которая гарантированно будет включена в эту выпуклую оболочку, построить векторы ко всем остальным точкам, выбрать из них самый правый, перейти на выбранную точку, повторить. Если уже выбраны две точки, ситуация облегчается: сумма нормированных векторов будет тем больше, чем больше они сонаправлены. Проблема только в выборе второй точки, потому что не на чем построить самый первый вектор. Но если самая первая точка — крайняя левая, то можно взять вертикальный вектор (добавить мнимую точку с той же координатой X, но с запредельным Y): все остальные точки будут гарантированно справа. Но векторы у меня вылетели из головы, а с тригонометрией и выбором самого маленького угла относительно только что построенной прямой я просто запутался. Время поджимало, и надо было сдать хоть какое-то решение. Результат поразил даже меня самого.
Итак, для получения бонусных очков надо показать всё это графически. Отлично: выводим на экран все введённые точки, между всеми ними рисуем линии. Тогда линии, составляющие выпуклую оболочку, тоже будут нарисованы. Теперь берём какую-нибудь точку, расположенную вне этой оболочки ([639, 479] кажется подходящим кандидатом) и выполняем заливку FloodFill кавайно-малиновым цветом. Заливка упрётся в линии выпуклой оболочки. Теперь ещё раз пройдёмся по всем возможным линиям, отрисовывая их уже чёрным цветом — с точки зрения пользователя линии сотрутся. На экране останется малиновый фон с чёрной кляксой посередине, а граница между ними как раз и будет внешней оболочкой. Бонусное задание выполнено.
Теперь для каждой точки найдём цвета восьми окружающих её пикселей. Если среди них окажутся малиновые, вызовем сложный комплекс проверок, призванный ответить на вопрос, является ли точка частью внешней оболочки или же просто лежит рядом с границей. Я не помню, как я обрабатывал граничные случаи, — кажется, сдвигал точку на пиксель в сторону чёрного цвета, перерисовывал и смотрел на разницу, — но в конечном итоге я находил все точки выпуклой оболочки (плюс, возможно, несколько лишних, лежащих совсем рядом с границей и не отсеянных дополнительными проверками). В конце концов я очищал экран и рисовал выпуклую оболочку набело, одной линией: мол, смотрите, завидуйте. Весь процесс занимал несколько минут.
Монстрообразная программа состояла из нескольких десятков функций с «говорящими» именами типа CheckThis и Try12. Комментариев по делу не было: мне было не до них. Переменные имели имена, в которых начал путаться я сам. Глобальные и локальные были замешаны в гремучую смесь. Времени на отладку и на доводку этого чуда до ума просто не хватило. Работает? Сдаём!
Комиссия долго совещалась по поводу оценки этого творения, но в конце концов согласилась, что задачу я выполнил, и начислила мне за неё какое-то количество баллов. Думаю, не в последнюю очередь на их решение повлиял рассказ про Нильса Бора, решающего задачу об измерении высоты башни с помощью барометра, который я по памяти вбил в комментарий в начале программы. По сумме баллов я занял на этой олимпиаде первое место.
Дома, в спокойной обстановке, я переписал решение как надо, с векторами и определением углов. Потом, переехав в другую страну и обучаясь на факультете компьютерных наук, я обнаружил ещё несколько решений этой задачи, в том числе очень оригинальный и довольно быстрый алгоритм Чана, созданный как раз в середине девяностых. Переписанная программа заняла в несколько раз меньше места, работала не в пример быстрее и выглядела куда элегантнее. А самое обидное, что реализация этого решения (даже с учётом повторения темы «векторы» в учебнике математики) заняла меньше времени.
Какой будет мораль? А не будет никакой морали. Разве что повторение общеизвестной истины: озаботьтесь проектированием перед тем, как начать писать код.
#5485: Те, что сдвигают с бородатой точки
19:45 17.02.2011, IT happens
Прочёл недавно историю «Об админизме в красках»[3]. Девушка, вы в перечне «кот, шредер, свитер, борода, пиво, джинсы, кеды, сигареты, отсутствие девушки, обожание компьютеров» не на то место отсутствие девушки поставили. Надо в начало. Админы формируются в то время, когда их субтильные тела не интересуют девушек абсолютно ни под каким соусом. Вдоволь наобламывавшись, люди в конце концов находят себе подобных, жизнь устаканивается, и от заходящих в серверную всех таких красивых не ждут ничего хорошего. Они даже не в курсе, что перспективных парней уже разобрали ваши более удачливые подруги, а альфа-самцы потихоньку начинают спиваться, и вы обратили свой благосклонный взор на бывших ботаников. А они, как назло, не рисуются перед вами, да и не перспективные ни фига.