这题应该是搜索吧，可是分类里分成了计算几何，哎，就发这吧~~
比较需要注意的是它能成为三角形要看原图的……不过这也减小了难度，本来是要上下搜的~~
搜索的策略是距开始的小三角为偶数的时候向上搜，否则向下搜，注意到搜索时底边只能为奇数，目标是找到最大的底边。
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
char tri[101][201];
int n;
bool Search( int flg, int a, int b, int l ){
if( (l&1)==0 ) return false;
int i, j;
if( flg&1 ){
if( l/2> a ) return false;
for( i= a-1; i>= a-l/2; i-- )
for( j= b+a-i; j< b+l-a+i; j++ )
if( tri[i][j]!='-' ) return false;
}
else{
if( l/2> n-a-1 ) return false;
for( i= a+1; i<= a+l/2; i++ )
for( j= b+i-a; j< b+l-i+a; j++ )
if( tri[i][j]!='-' ) return false;
}
return true;
}
int main(){
int i, j, k, max, t= 1;
while( scanf("%d",&n) && n ){
max= 0;
getchar();
for( i= 0; i< n; i++ )
gets(tri[i]);
for( i= 0; i< n; i++ ){
if( n-i<= max/2 ) break;
for( j= i, k= 0; j< 2*n-i-1; j++ ){
if( tri[i][j]=='-' ){
k++;
if( (k&1) && k> max )
if( Search(i+j,i,j-k+1,k) ) max= k;
else k--;
}
else k= 0;
}
}
printf("Triangle #%d\nThe largest triangle area is %d.\n\n",t++,(max+1)*(max+1)/4);
}
return 0;
}posted on 2009-06-27 21:28
古月残辉 阅读(542)
评论(1) 编辑 收藏 引用 所属分类:
计算几何