现在的位置: 首页 > 综合 > 正文

HDU 2050 折线分割平面

2019年02月24日 ⁄ 综合 ⁄ 共 789字 ⁄ 字号 评论关闭

题目链接~~>

做题感悟:   

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

题意:      

         给你 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 ;
}

 

 

 

 

 

抱歉!评论已关闭.