Илие Падурару подготвя завещанието си. Той има двама сина и две дъщери. Илие иска да раздели честно притежавания участък гора между децата си. За целта той начертава правоъгълна карта, представяща гората и с по едно кръгче отбелязва всяко дърво. Картата може да се зададе като двумерен масив с размер NxM, съдържаща P дървета, както е показано на рисунка а), където всяко дърво е отбелязано с l. Илие иска да построи огради, които пресичат гората под ъгъл 45 градуса, така че всяка оградена площ да съдържа еднакъв брой дървета (виж рисунки b) и c).
Задача
a.
Определете краищата на оградата която разделя гората на две
части с по равен брой дървета. (рисунка b))
b.
Определете краищата на две перпендикулярни огради, които
разделят гората на четири части,
всяка съдържаща по равен брой дървета (рисунка
c))
Вход
Входният файл copaci.in
съдържа на първия си ред трите положителни цели числа, N
M P, разделени с по един интервал, като
N
задава броя на редовете в масива, представящ гората, M
- броя на стълбовете,
а
P
- броя на дърветата.
Всеки от следващите
P реда във файла
съдържа две положителни цели числа, разделени с интервал: x
и
y, които задават позицията на поредното дърво (x
е индекс, определящ номер на реда, а
y е индекс,
определящ номер на стълба в матрицата). Редовете са
номерирани от 1
до N,
а стълбовете - от
1
до M.
Изход
Изходният файл copaci.out
трябва да съдържа два реда. Първият ред трябва да съдържа 4
положителни цели числа, разделени с по един интервал, x1 y1 x2 y2,
където (x1,y1)
и (x2,y2)
представят краищата на оградата от задача a.
Вторият ред трябва да съдържа 8
положителни цели числа, разделени с по един интервал, x3
y3 x4 y4 x5 y5 x6
y6, където (x3,y3),
(x4,y4)
представят краищата на първата ограда, а (x5,y5),
(x6,y6)
представят крайщата на втората ограда (перпендикулярна на
първата) - решение на задача b.
За всеки край на оградата, първият индекс трябва да задава
номера на реда (x),
а вторият - номера на стълба (y).
Ако за някоя от задачите няма решение, програмата трябва да
изведе само една стойност
-1
на съоветния ред във файла.
Ограничения
Примери
copaci.in | copaci.out(възможно решение) | copaci.in | copaci.out(възможно решение) | copaci.in | copaci.out(възможно решение) |
6 8 4 |
6 2 1 7 6 2 1 7 1 2 6 7 |
7 10 4 1 9 2 10 5 9 3 9 |
1 8 3 10 -1 |
8 8 4 1 5 3 8 5 2 8 3 |
1 1 8 8 1 2 7 8 8 2 2 8 |
Time limit: 0.5 сек/тест
prof. Serban Marinel
"Gr. C. Moisil" Iaşi IT High School
marinel_serban@yahoo.com
Превод на български: Емил Келеведжиев