О барометре в свободном падении

Говорите, программа рассчитывает принадлежность клетки к одной или другой группе по цвету фона? Ха! Нас этим не удивить.

Начало девяностых, олимпиада по информатике для школьников в далёкой провинции России. Одно из заданий: построить и вывести на экран решение задачи о выпуклой оболочке для произвольного массива из не менее чем трёх точек в двухмерном пространстве, никакие три из которых не лежат на одной прямой. Решением должен быть список точек, составляющих эту выпуклую оболочку, в произвольном порядке. В качестве бонуса можно было продемонстрировать всю эту чушь в графическом виде.

Для справки: задача важная, нужная и популярная, и решений у неё есть много. Одно из решений приведено в книге «Алгоритмы: построение и анализ» Т. Кормена, являющейся университетским учебником для большинства вузов, начиная с MIT. Но в девяностых на окраине России про Кормена ещё не знали, и пришлось выкручиваться своими силами.

Насколько я понимаю, от нас ожидалось что-то вроде алгоритма Грэхема: взять самую левую точку, которая гарантированно будет включена в эту выпуклую оболочку, построить векторы ко всем остальным точкам, выбрать из них самый правый, перейти на выбранную точку, повторить. Если уже выбраны две точки, ситуация облегчается: сумма нормированных векторов будет тем больше, чем больше они сонаправлены. Проблема только в выборе второй точки, потому что не на чем построить самый первый вектор. Но если самая первая точка — крайняя левая, то можно взять вертикальный вектор (добавить мнимую точку с той же координатой X, но с запредельным Y): все остальные точки будут гарантированно справа. Но векторы у меня вылетели из головы, а с тригонометрией и выбором самого маленького угла относительно только что построенной прямой я просто запутался. Время поджимало, и надо было сдать хоть какое-то решение. Результат поразил даже меня самого.

Итак, для получения бонусных очков надо показать всё это графически. Отлично: выводим на экран все введённые точки, между всеми ними рисуем линии. Тогда линии, составляющие выпуклую оболочку, тоже будут нарисованы. Теперь берём какую-нибудь точку, расположенную вне этой оболочки ([639, 479] кажется подходящим кандидатом) и выполняем заливку FloodFill кавайно-малиновым цветом. Заливка упрётся в линии выпуклой оболочки. Теперь ещё раз пройдёмся по всем возможным линиям, отрисовывая их уже чёрным цветом — с точки зрения пользователя линии сотрутся. На экране останется малиновый фон с чёрной кляксой посередине, а граница между ними как раз и будет внешней оболочкой. Бонусное задание выполнено.

Теперь для каждой точки найдём цвета восьми окружающих её пикселей. Если среди них окажутся малиновые, вызовем сложный комплекс проверок, призванный ответить на вопрос, является ли точка частью внешней оболочки или же просто лежит рядом с границей. Я не помню, как я обрабатывал граничные случаи, — кажется, сдвигал точку на пиксель в сторону чёрного цвета, перерисовывал и смотрел на разницу, — но в конечном итоге я находил все точки выпуклой оболочки (плюс, возможно, несколько лишних, лежащих совсем рядом с границей и не отсеянных дополнительными проверками). В конце концов я очищал экран и рисовал выпуклую оболочку набело, одной линией: мол, смотрите, завидуйте. Весь процесс занимал несколько минут.

Монстрообразная программа состояла из нескольких десятков функций с «говорящими» именами типа CheckThis и Try12. Комментариев по делу не было: мне было не до них. Переменные имели имена, в которых начал путаться я сам. Глобальные и локальные были замешаны в гремучую смесь. Времени на отладку и на доводку этого чуда до ума просто не хватило. Работает? Сдаём!

Комиссия долго совещалась по поводу оценки этого творения, но в конце концов согласилась, что задачу я выполнил, и начислила мне за неё какое-то количество баллов. Думаю, не в последнюю очередь на их решение повлиял рассказ про Нильса Бора, решающего задачу об измерении высоты башни с помощью барометра, который я по памяти вбил в комментарий в начале программы. По сумме баллов я занял на этой олимпиаде первое место.

Дома, в спокойной обстановке, я переписал решение как надо, с векторами и определением углов. Потом, переехав в другую страну и обучаясь на факультете компьютерных наук, я обнаружил ещё несколько решений этой задачи, в том числе очень оригинальный и довольно быстрый алгоритм Чана, созданный как раз в середине девяностых. Переписанная программа заняла в несколько раз меньше места, работала не в пример быстрее и выглядела куда элегантнее. А самое обидное, что реализация этого решения (даже с учётом повторения темы «векторы» в учебнике математики) заняла меньше времени.

Какой будет мораль? А не будет никакой морали. Разве что повторение общеизвестной истины: озаботьтесь проектированием перед тем, как начать писать код.