HIDTRI - Hidden Triangle

no tags 

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 45o, 90o or 135o, thus forming right-angled isosceles triangles. The existence of hidden right-angled isosceles triangles in an array is illustrated in the figure below.

\epsfbox{p3258.eps}

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 i-th line gives the i-th 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 right-angled 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


Kanpur-Kolkata 2004-2005


hide comments
Duc: 2009-10-27 16:18:34

There's no limit on the original problem but FYI the largest test case has m=n=500

Adhiraj Somani: 2009-08-03 07:13:21

What are the limits on m and n ?


Added by:Duc
Date:2008-12-09
Time limit:0.136s-0.363s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Kanpur 2004