随笔-20  评论-16  文章-36  trackbacks-0
      网上都评价说这题不难,没什么算法,是道水题,可是我看了别人的代码后,感觉收获还是比较大的,就发了。
      这题先是求积分,高中物理都能搞定的,把dl=rdă代入就能求得I=ă*k*h,其中ă是每条边对原点夹的角,比如对边AB,它的ă就是<AOB。那么下面的问题就转化为整个图形对原点所夹的角的最大值,这里可能有个问题,比如对于一个螺旋型的Fence,原点在中心,那么可能求出的夹角大于2*PI,由于Fence是不能透光、反射、散射的,因此最大值只能为2*PI。又由于Fence不能经过原点,因此每条边的夹角在-PI~PI之间,这里求整个图形对原点所夹的角用了一个很强的方法,可以保证无论从哪个点开始算,只要是按顺序,它一定能求得最大的角度(我领悟了半天啊),而且min一定要初始化为0而不是2*PI等大于0的数,考虑下原点在图形内部的情况就知道了~~至于正确性,可以自已画个图就能理解了~~
      下面是我的实现代码,参考了网上代码~~

#include <iostream>
#include 
<cmath>
using namespace std;
#define PI 3.1415926
double Angle( double x0, double y0, double x1, double y1 ){
     
double a= atan2(y0,x0);
     
double b= atan2(y1,x1);
     
if( b-a> PI ) a+= 2*PI;    //将夹角映射到-PI~PI之间
     if( a-b> PI ) b+= 2*PI;
     
return a-b;
}


int main(){
    
double h, k, x[101], y[101], max= 0, min= 0, sum= 0;
    
int n, i;
    scanf(
"%lf%lf%d",&k,&h,&n);
    
for( i= 0; i< n; i++ )
        scanf(
"%lf%lf",&x[i],&y[i]);
    x[n]
= x[0], y[n]= y[0];
    
for( i= 0; i< n; i++ ){      //精髓啊
        sum
+= Angle(x[i],y[i],x[i+1],y[i+1]);
        
if( sum< min )    min= sum;
        
if( sum> max )    max= sum;
        
if( max-min>= 2*PI ){
            max
= min+ 2*PI;
            
break;
        }

    }

    printf(
"%.2lf\n",(max-min)*k*h);
    
return 0;
}
posted on 2009-06-26 10:58 古月残辉 阅读(2357) 评论(3)  编辑 收藏 引用 所属分类: 计算几何

评论:
# re: POJ 1031 Fence 2010-08-24 17:26 | Zeno
dI=I0*|cosα|*dl*h中的|cosα|被无视了么?  回复  更多评论
  
# re: POJ 1031 Fence 2010-08-24 17:30 | Zeno
就算dl=rdă代入dI=I0*|cosă|*dl*之后也是dI=k*h*|cosă|*dă呀,为什么会解出I=ă*k*h来?  回复  更多评论
  
# re: POJ 1031 Fence 2011-03-14 20:45 | dereky
不明白那个公式是怎么推出来的  回复  更多评论
  

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