0 人解决，3 人已尝试。
0 份提交通过，共有 21 份提交。
9.9 EMB 奖励。
单点时限: 10.0 sec
内存限制: 256 MB
Squad commander is looking for a location to build a camouflaged camp of a certain size. He has a digital topographic map of the area, which is a rectangular grid with every element defining the altitude at a certain coordinate. Coordinates of any point on the map are identified by the row and the column in the table.
2 2 2 2 2 2
2 6 6 4 3 2
3 5 8 7 7 4
4 6 8 9 8 6
5 7 8 8 8 7
The camp location should be a rectangle fully located within the map area and satisfy certain characteristics. Each characteristic consists of two identical adjacent rectangular areas and the requirement for their altitudes. It is defined by
location, i.e. the coordinates of the top-left corner of the first (i.e. the left or the top) rectangular area; The coordinates are given in respect of the camp area.
size (length and width) of the first (and the second because they are equal) rectangular areas;
rectangle arrangement flag, 0 indicates horizontal arrangement of the rectangular areas (i.e. areas have common vertical side), while 1 – vertical arrangement (i.e. areas have common horizontal side);
altitude flag, 0 indicates that the average altitude of the first (i.e. the left or the top) rectangular area should be strictly less (<) than the average altitude of the second. 1 indicates the opposite (>=) situation.
2 2 2 2 2 2
2 6 6 4 3 2
3 5 8 7 7 4
4 6 8 9 8 6
5 7 8 8 8 7
Characteristic A:
Location – (1, 1)
Size – (1, 3)
Arrangement flag: 1
Altitude flag: 0
The selected location satisfies characteristic A.
2 2 2 2 2 2
2 6 6 4 3 2
3 5 8 7 7 4
4 6 8 9 8 6
5 7 8 8 8 7
Characteristic B:
Location – (2, 2)
Size – (2, 2)
Arrangement flag: 0
Altitude flag: 0
The selected location does not satisfy characteristic B.
The camp location satisfies the characteristic if the altitude requirement is satisfied.
Write a program which given the topographic map of the area and the characteristics would find the best (the one that satisfies most characteristics) location for building the camouflaged camp. In case of several solutions, output any of them.
The first line contains two integers R and C (2<= R,C<= 1000). They correspond to the number of rows and columns in the topographic map. The following R lines with C nonnegative integer numbers in each of them describe the topographic map. The altitude does not exceed 255 at any coordinate.
Two integer numbers L (number of rows) and W (number of columns) (1<= L,W<= 1000; L <= R; W<= C) defining the size of the camp are written in the following line.
The next line contains one integer H (1<= H<= 1000) – the number of characteristics.
Finally, the following H lines describe characteristics. Each of them contains 6 integers: coordinates of the characteristic’s top-left corner, size of the first rectangular area, the arrangement and the altitude flags. All characteristics fit within the camp.
The first line of the output should contain two integers – the coordinates of top-left corner of camp location.
5 6 2 2 2 2 2 2 2 6 6 4 3 2 3 5 8 7 7 4 4 6 8 9 8 6 5 7 8 8 8 7 3 5 3 1 1 1 3 1 0 2 2 2 2 0 0 2 4 1 1 1 1
3 1 Hint: Location (3, 1) satisfies all three characteristics
0 人解决，3 人已尝试。
0 份提交通过，共有 21 份提交。
9.9 EMB 奖励。