Geometrical
Shapes
Young Gigel has just learnt during the geometry class,
what the square and the diamond look like. After this first class, when all the
pupils were still puzzled, the teacher gave them a weird task
: he gave them a binary matrix with N rows & N columns. The teacher asked
the students to find the largest square (in terms of area) which contains only
1s and the largest diamond (also in terms of area) which contains only 1s.
Because the diamonds can be defined in so many ways, in this problem, you will
consider that a diamond is
a square rotated by 45
degrees (see the pictures for a clear view).
### PICTURES ###
Square with side 1 Square with side
2 Square with side 3
Diamond with side 1 Diamond with side
2 Diamond with
side 3
Your task is to find the length of the side of the
largest square and the number of different squares with the largest area and the
length of the side of the largest diamond and the number of different diamonds
with the largest area.
Input
Data
The first line of the input file FIGURES.IN will contain
the number of rows & columns of the matrix. The next N lines will contain N
integer values from the set {0,1}, unseparated by
blanks.
Output
Data
The first line of the output file FIGURES.OUT will contain
2 integers: LS and NS - the side of the largest square and the number of squares
with the largest area - separated by a blank. On the second line there will be
2 more integers: LD and ND - the side of the largest diamond and the number of
diamonds with the largest area - separated by a blank.
Limits
·
3 <= N <= 255
·
A square with the top-left corner at coordinates
(row i,column j) and side L, has the property that all
the unit squares of the matrix with coordinates (i+p,j+q), 0<=p,q<=L, are
marked with 1.
·
A diamond with the centre (i,j)
and side L has the property that all the unit squares of the matrix with
coordinates (i+p,j+q), |p|+|q| < L
are marked with 1.
·
The score for every test is distributed as
follows:
- 15% , if LS is
correct
- 15% , if NS is
correct
- 35% , if LD is
correct
- 35% , if ND is
correct
Example:
FIGURES.IN FIGURES.OUT
6 3
4
001101 3
3
111111
111111
011111
001110
111100
Explaination:
·
In the example above, the squares with side 3
have the top-left corners at the coordinates (row,column): (2,2) ; (2,3) ;
(2,4) ; (3,3).
·
In the example above, the diamonds with side 3
have their centres at the coordinates (row,column): (3,3) ; (3,4) ; (4,4).
Time limit: 0.5
seconds/test case