求三角形最大面积问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

圣诞节快到了。你接受了一件光荣的任务,就是制作圣诞树顶上的那颗大星星。不过当你拿到制作用的三角形银纸的时候,你发现银纸上面有许多洞。原来你的妹妹已经在银纸上剪下了一些小的三角形来制作小星星。你唯有寻找一个算法,告诉你在每张银纸上还能切出来的最大三角形面积。

给定一个三角形,里面有黑色和白色的区域,你必须找到白色的区域中最大三角形的面积,如图1所示: 

 

Input

输入数据包含对若干个三角形的描述。每个三角形描述的第1行是一个整数n(1<=n<=100),表示该三角形的高。接下来的n行每行包含由空格、“#”和“-”组成的字符串表示三角形的状况。其中“#”代表黑色的区域,“-”代表白色的区域。空格是用来填充输入的左边,从而使得整个输入构成一个三角形的形状。

对每个三角形,每行字符“#”和“-”的数目之和都是奇数,由2n-1递减至1。

全部输入以n=0结束。

Output

对输入的每个三角形,输出白色的区域中最大三角形的面积。注意,最大三角形可以是定焦朝上的,如同第2个样例输入所示。

Sample Input

5
#-##----#
 -----#-
  ---#-
   -#-
    -
4
#-#-#--
 #---#
  ##-
   -
0

Sample Output

9
4

Hint

Source