Задача 3

Задача 3. Информат= ;изация садоводствk= 2;

Имя входного файла:	garden.in
Имя выходного файла:	garden.out
Максим&= #1072;льное время работы на одном тесте:<= /p>	2 секунды
Максим&= #1072;льный объем используем= 086;й памяти:	64 мегабайта
Макси = 84;альная оценка	100 баллов

Дачный участок Степана Петровича имеет форму прямоугольl= 5;ика размером a = ´ b= . На участке имеется n построеl= 2;, причем осно = 74;ание каждой постройки — прямоугольl= 5;ик со сторонам = 80;, параллельнm= 9;ми сторонам уч = 72;стка.

Вдохновl= 3;енный успехами соседей, Степан Петр = 86;вич хочет посадить на своем участке m&n= bsp;видов плодовых культур (участок Степана Петровича находится в северной местности, поэтому m =3D 1 или m =3D 2). Д = 83;я каждого вид = 72; растений Степан Петрович хочет выделить отдельную прямоугольl= 5;ую грядку со сторонами, параллельнm= 9;ми сторонам участка. Сам= 086; собой, грядк= 080; не могут зан= 080;мать территорию, занятую пос = 90;ройками или другими грядками.

Степан П = 77;трович хочет расположитn= 0; грядки таким образом, чтобы их сум= 084;арная площадь был = 72; максимальнl= 6;й. Грядки не должны пересекатьl= 9;я, но могут кас= 072;ться друг друга.

грядка №1
дом
сарай	грядка №2=

Требуетl= 9;я написать программу, которая по заданным размерам уч = 72;стка и координатаl= 4; построек определяет оптимальноk= 7; расположенl= 0;е планируемыm= 3; грядок.

Формат входных данных

В первой строке входного файла содержатся два целых числа n и m (0 ≤ n ≤ 10; 1 &= #8804; m ≤ 2).

Во второ = 81; строке содержатся два целых чи= 089;ла a и b (= 1 ≤ a, b ≤ 10000).

Далее следуют n строк, каждая из которых содержит четыре целы = 93; числа x_i,1, y_i_,1, x_i<= /span>_,2, y_i_,2 –коо&#= 1088;динаты двух противополl= 6;жных углов постр = 86;йки (0 = £ x_i_,1< x_i<= /span>_,2= £ a, 0 £ y_i,1 < y_i_,2 £ b). Различн = 99;е постройки н = 77; могут пересекатьl= 9;я, но могут касаться друг друга.

Формат выходных данных

В выходной файл необхо = 76;имо вывести m строк, каждая из которых содержит координаты двух противополl= 6;жных углов предп = 86;лагаемой грядки. Координаты должны быть = 094;елыми (всегда можн= 086; добиться максимальнl= 6;й суммарной площади гря = 76;ок, располагая их в прямоугольl= 5;иках с целыми координатаl= 4;и).

В случае, если в вашем решении Степану Пет = 88;овичу следует рас = 87;оложить менее m грядl= 6;к, необходимо = 74;ывести для грядок, которые не следует сажать, стро= 082;у «0 0 0 0» (см. второ&= #1081; пример ниже).

Примеры входных и выходных данных

garden.in

garden.out

2 2

7 5

4 2 6 4

0 1 2 2

0 2 4 5

2 0 7 2

3 2=

4 4

0 0 4 1

0 1 1 4

3 1 4 4

1 1 3 4

0 0 0 0

Замечан = 80;е о системе оценки

Решения, рассматривk= 2;ющие только случай m=3D1, б= 091;дут оцениватьсn= 3; из 50 баллов.