http://poj.org/problem?id=1471
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
#define MAXNO 102
int tr[MAXNO][2*MAXNO-1]={0};
int maxtr[MAXNO][2*MAXNO-1]={0};
int curmax=0;
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
int sum(int a1,int an,int n)
{
return (a1+an)*n/2;
}
int ln(int n)
{
return 2*n-1;
}
int mingrid(int l,int r,int d)
{
if(d)
return min(l,r)+1;
else
return 1;
}
int main()
{
int N,i,j,l,r,d,di,k=1;
int nsum,nline;
char s[(1+MAXNO)*MAXNO/2];
cin>>N;
while(N)
{
curmax=0;
nsum=sum(1,N,N);
nline=ln(N);
for(i=1;i<=N;i++)
{
for(j=1;j<=nline;j++)
{
tr[i][j]=0;
maxtr[i][j]=0;
}
}
for(i=1;i<=N;i++)
{
cin>>s;
for(j=1;j<=ln(N-i+1);j++)
{
if(s[j-1]=='-')
tr[i][j+i-1]=1;
}
}
for(i=1;i<=nline;i++)
{
maxtr[1][i]=tr[1][i];
if(curmax<maxtr[1][i])
curmax=maxtr[1][i];
}
if(N>1)
{
maxtr[N][N]=tr[N][N];
for(i=2;i<=N;i++)
{
for(j=i;j<=nline-i+1;j++)
{
if((j+!(i%2))%2)
{
l=maxtr[i-1][j-1];
r=maxtr[i-1][j+1];
d=tr[i-1][j];
if(tr[i][j])
maxtr[i][j]=mingrid(l,r,d);
if(curmax<maxtr[i][j])
curmax=maxtr[i][j];
}
}
di=N-i+1;
for(j=di;j<=nline-di+1;j++)
{
if((j+!(di%2))%2==0)
{
l=maxtr[di+1][j-1];
r=maxtr[di+1][j+1];
d=tr[di+1][j];
if(tr[di][j])
maxtr[di][j]=mingrid(l,r,d);
if(curmax<maxtr[di][j])
curmax=maxtr[di][j];
}
}
}
}
cout<<"Triangle #"<<k<<endl;
cout<<"The largest triangle area is "<<curmax*curmax<<'.'<<endl;
cout<<endl;
cin>>N;
k++;
}
return 0;
}