HDU 2050 折线分割平面

题目链接~~>

做题感悟：   

                 一开始的想法是找规律，但是后来没坚持下来。应该多思考一下的！！

题意：      

         给你 n 条折线能把一个平面分成几部分。

解题思路：

              方法一：先看N条直线能把一个平面分成几部分，当添加第N条只直线时，为了使平面最多，则第N条直线要与前面的N-1条直线都相交，且没有任何三条直线交于一个点。则第N条直线有N-1个交点。由于每增加N个交点，就增加N+1个平面，所以用N条直线来分隔平面，最多的数1+1+2+3……+n=1+(n+1)*n/2 ;再看每次增加两条相互平行的直线，当第N次添加时，前面已经有2N-2条直线了，所以第N次添加时，第2N-1条直线和第2N条直线都各能增加2*（n-1）+1 个平面。所以总平面为：1+4*n(n+1)/2-2*n=2*n*n+1 ;如果把每次加进来的平行边让它们一头相交每一组平行线相交后，就会减少一个面，所以所求就是平行线分割平面数减去N，为2*n*n-n+1，利用上述总结公式 f( n ) = 2*n*n - n + 1 。

            方法二：分割平面的个数=交点个数+顶点个数+1。令f(n-1)为前n-1条折线分割的平面数，当添加第n条折线时。因为每一条边与前n-1条折线的两条边都相交，故增加的交点数为2*2*(n-1)，顶点增加1，故 f(n)=f(n-1)+4(n-1)+1。
代码：（方法二）

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      int f[10005] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,n ;
     
    
   

    

     

    
    

     

       f[1]=2 ;
     
    
   

    

     

    
    

     
 for(int i=2 ;i<=10000 ;i++)
     
    
   

    

     

    
    

     

       f[i]=f[i-1]+4*(i-1)+1 ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&n) ;
     
    
   

    

     

    
    

     
 printf("%d\n",f[n]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/16806773