алгоритмическая задачка
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}
Re: Жызнено
Date: 2008-04-23 10:36 am (UTC)Давайте рекурсивно.
Пусть R(i) кол-во незаконченых прямоугольнников после i точек.
Тогда:
R(i+1) = R(i)
+ 1 //Новый с левым краем.
+ 2*In(i+1) - In(i+1) //Те, кого пересекли i+1 точкой.
А какой порядок у In(i)? Интуитивно вижу "лесенку" из вложеных прямоугольников. In(i) = O(i) вероятно?
Тогда, да. На каждом шагу. O(n * log n).