随笔-20  评论-16  文章-36  trackbacks-0
      这题应该是搜索吧,可是分类里分成了计算几何,哎,就发这吧~~
      比较需要注意的是它能成为三角形要看原图的……不过这也减小了难度,本来是要上下搜的~~
      搜索的策略是距开始的小三角为偶数的时候向上搜,否则向下搜,注意到搜索时底边只能为奇数,目标是找到最大的底边。
#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)  编辑 收藏 引用 所属分类: 计算几何

评论:
# re: POJ 1471 Triangles 2011-03-26 20:54 | zephyr
谢谢指点,原来没有仔细地考虑图的真实情况,一直WA,发现画出来的图和输入的情况大不一样  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理