HIDTRI  Hidden Triangle
Assume that each `0' or `1' in the array represents a point on a plane and the distance between each pair of neighbouring points row wise or column wise is unity. Assume further that every neighbouring pair of 1's, row wise, column wise or diagonally is connected by a line segment. Two line segments emerging from a point, either join together to form a longer line segment or form an angle of 45^{o}, 90^{o} or 135^{o}, thus forming rightangled isosceles triangles. The existence of hidden rightangled isosceles triangles in an array is illustrated in the figure below.
Input
Input consists of multiple test cases.
For each test case the first line gives three integers: the case number k, the number of rows m and the number of columns n of the given array. A space appears between two neighbouring integers.
Each of the next m lines gives a string of 0's and 1's of length n; the ith line gives the ith row of the array.
Input terminates with a value zero for case number k.
Output
For each test case, display output in one line. The line contains the case number k and the area of the largest rightangled isosceles triangle hidden in the array. The area is a real number with one digit after the decimal point. If a triangle does not exist then output `0.0' as the area.
Sample Input
1 3 3 101 100 101 2 4 6 001001 010101 111111 000001 0
Sample Output
1 0.0 2 4.0
KanpurKolkata 20042005
hide comments
Duc:
20091027 16:18:34
There's no limit on the original problem but FYI the largest test case has m=n=500 

Adhiraj Somani:
20090803 07:13:21
What are the limits on m and n ? 
Added by:  Duc 
Date:  20081209 
Time limit:  0.136s0.363s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM Kanpur 2004 