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

[avva]

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

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

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

Comments

[spartach.livejournal.com]

Точек не очень много? Я бы добавлял их по одной. Когда стоит одна точка, есть четыре возможных максимальных прямоугольника (слева-сверху-справа-снизу от этой точки); при постановке каждой новой точки каждый из прямоугольников, на которые она попала, аналогично заменяем на четыре. Все время, таким образом, храним все потенциально максимальные многоугольники.

[avva.livejournal.com]

Суть в том, чтобы построить алгоритм, достаточно быстро работающий как фунцкия от n (числа точек).

[spartach.livejournal.com]

Да уж, у меня в худшем случае что-то вроде O(2^n) операций выходит. Не катит:)