алгоритмическая задачка
Apr. 23rd, 2008 12:17 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva(будет интересно только программистам)
На работе рассказали интересную задачу. Пусть дан прямоугольный лист металла известных размеров. Из-за дефектов производства на листе есть точки, в которых металл слишком слаб - дан список таких точек, с координатами каждой. Задача: найти наибольший по площади прямоугольник внутри листа, не содержащий ни одной дефективной точки внутри себя (на границе - можно).
Искать следует только среди прямоугольников со сторонами, параллельными исходному (более общий вопрос, в котором искомый прямоугольник может быть повернут относительно всего листа, можно считать отдельной задачей - ее я вообще не знаю, как решать).
На работе рассказали интересную задачу. Пусть дан прямоугольный лист металла известных размеров. Из-за дефектов производства на листе есть точки, в которых металл слишком слаб - дан список таких точек, с координатами каждой. Задача: найти наибольший по площади прямоугольник внутри листа, не содержащий ни одной дефективной точки внутри себя (на границе - можно).
Искать следует только среди прямоугольников со сторонами, параллельными исходному (более общий вопрос, в котором искомый прямоугольник может быть повернут относительно всего листа, можно считать отдельной задачей - ее я вообще не знаю, как решать).
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2008-04-23 01:39 pm (UTC)x[i], y[i] - координаты точки, имеющей порядковый номер i в списке, отсортированном по возрасатанию x.
t и b равны следующему
t[a,b] = min (y[c] : y[c]>=y[a], x[a]<=x[c]<=x[b])
b[a,b] = max (y[c] : y[c]<=y[a], x[a]<=x[c]<=x[b])
Считаются рекурсивно так за n^2
t[a,b] = (y[b-1]>y[a]) ? min(t[a,b-1],y[b-1]) : t[a,b-1]
b[a,b] = (y[b-1]<y[a]) ? max(b[a,b-1],y[b-1]) : b[a,b-1] Ответ - max( (t[a,b] - b[a,b]) * (x[b]-x[a]) )