рекурсия- разбиение и сборка квадрата Опции

[Екатерина7]

помогите, пожалуйста, разобраться с задачей

Лист бумаги в клетку квадратной формы размера NxN произвольно разрезан на прямоугольные части, каждая из которых имеет целое число клеток. Полученные прямоугольные куски перемешаны. Требуется из заданных прямоугольников снова составить квадрат. Квадрат не обязательно должен быть составлен из прямоугольников в том же порядке, в каком он разрезан. При сборке прямоугольники можно поворачивать.

(число N не задано, можно брать любое)

[Lapp]

Не знаю, как с точки зрения Екатерина7, но лично мне нравится, что обсуждение получилось оживленным )). Также спасибо volvo за осторожные коррекции направлений.

Unconnected пошел хитрым путем, решив, что "против лома нет приема". Если математические соотношения становятся слишком сложными - будем решать тупо в лоб: массивы координат, смотрим наличие в них одинаковых. Способ чрезвычайно ресурсоемкий и совершенно непригодный для случая непрерывных координат (что, впрочем, тут не нужно).

Archon говорит в принципе верные вещи, но они мало отличаются от того, что завело в тупик Неприсоединенного. Слишком много проверок.

Катя, дальше следи внимательно, и если что-то неясно - говори.

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

Теперь обсудим другую ситуацию, тоже не совсем прямо вытекающую из условий задачи; а именно - отрезки на прямой. По сути, отрезок на прямой - это есть КРУГ в одномерном пространстве. И хотя обычно, говоря об отрезке, мало кто специально указывает положение его центра (как в случае окружности), он у него все же есть )). Давайте будем описывать отрезки не как обычно (началом и концом), а их центрами и радиусами (радиус отрезка равен половине его длины). И сразу же становится понятно, что условие пересечения двух отрезков на прямой записывается точно так же, как и кругов на плоскости. И не надо проверять несколько случаев.. ))

Дальше. Фактически, условие пересечения двух прямоугольников распадается на два условия по координатам, причем нужно брать их логическое пересечение (условие выполнено только когда оба условия по координатам отдельно выполнены) - это легко понять, нарисовав несколько случаев на бумажке(или снова в уме)).

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



|C₂ - C₁| <= L₁/2 + L₂/2

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

( 2*|Cx₂-Cx₁| <= Lx₁ + Lx₂ ) /\ ( 2*|Cy₂-Cy₁| <= Ly₁ + Ly₂ )


Катя, ты поняла математику? пожалуйста, ответь.


Ну вот, теперь можно переходить к программированию..
Я немного изменил названия переменных - извиняюсь за это, просто я тогда поспешил. Для однообразия лучше иметь вместо lx и ly однобуквенные идентификаторы a и b для длины и ширины. Вллюще, это не в полном смысле длина и ширина, а просто размер по x (это a) и по y (это b).

В итоге пресловутая функция будет выглядеть примерно так:

type
  tRectangle=record
    a,b: integer
  end;
  tLocation=record
    x,y: integer
  end;

function Overlap(r1: tRectangle; l1: tLocation; r2: tRectangle; l2: tLocation): boolean;
begin
  Overlap:=
    (Abs(l2.x*2+r2.a-l1.x*2-r1.a) < r1.a+r2.a) and
    (Abs(l2.y*2+r2.b-l1.y*2-r1.b) < r1.b+r2.b)
end;

Unconnected, спасибо за аллюзию, я appreciate that )).

Катя, пожалуйста, посмотри все и задавай вопросы. В принципе, мы готовы двигаться дальше, и следующим шагом будет как раз та подготовка входных данных, о которой шла речь выше. У кого какие соображения?