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