Ilie Paduraru is drafting his will. He has two boys and two girls, and he owns a small stretch of forest. Ilie wants to divide his fortune so he is fair with all his children. That's why he has drawn a rectangular map representing his stretch of forest and has marked each tree as a circle. Ilie's map can be represented as a two-dimensional array of size NxM like in image a), each of the P trees being represented by a l. It is Ilie's wish to be able to build fences that cross the forest diagonally, at a 45° angle, so that each fenced area contain the same number of trees (images b) and c)).
Task
a. Determine the extremities of a fence that divides the forest into two areas that contain the same number of trees (b))
b. Determine the extremities of two perpendicular fences that divide the forest into four areas that each contain the same number of trees (c)).
Input Data
Input file copaci.in contains
on the first line 3 positive integers, N
M P, each separated by a space, representing N
- the number of lines of the array representing the forest, M
- the number of columns, and P
- the number of trees in the forest.
Each of the following P lines
each contains two positive integers separated by a space, x
y, representing the positions of the P
trees (x is the line index and
y is the column index). The lines
are numbered from 1 to N
and the columns are numbered from 1
to M.
Output Data
Output file copaci.out will contain two lines. Line one will contain 4 positive integers each separated by a space, x1 y1 x2 y2, where (x1,y1) and (x2,y2) represent the extremities of the fence from task a.
Line two will contain 8 positive integers each separated by a space, x3
y3 x4 y4 x5 y5 x6
y6, where (x3,y3),
(x4,y4) represent the extremities
of the first fence and (x5,y5),
(x6,y6) represent the extremities
of the second fence (perpendicular to the first), fences which represent the
solution for task b.
For each extremity the first number specified is the line index (x),
followed by the column index (y).
If for one of the tasks there is no solution, the line will contain only
value -1.
Constraints
Examples
| copaci.in | copaci.out(possible solution) | copaci.in | copaci.out(possible solution) | copaci.in | copaci.out(possible solution) |
|
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 seconds/test
prof. Serban Marinel
"Gr. C. Moisil" Iaşi IT High School
marinel_serban@yahoo.com