April 23rd, 2008

moose, transparent

алгоритмическая задачка

(будет интересно только программистам)

На работе рассказали интересную задачу. Пусть дан прямоугольный лист металла известных размеров. Из-за дефектов производства на листе есть точки, в которых металл слишком слаб - дан список таких точек, с координатами каждой. Задача: найти наибольший по площади прямоугольник внутри листа, не содержащий ни одной дефективной точки внутри себя (на границе - можно).

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

мимоходом

Сидя в кафе, бросил взгяд на ноутбук девушки за соседним столиком - там была открыта заглавная страница google.com, и она вводила какую-то строку поиска. Поймал себя на том, что продумываю, на какие сервера придет этот запрос, какая сейчас нагрузка, как быстро будет ответ итп.

Всюду станки, да.