简单计算几何 hdu-4491 Windmill Animation-白红宇

简单计算几何 hdu-4491 Windmill Animation

阅读量：5375 次

发布时间：2019-06-15

本文共 2143 字，大约阅读时间需要 7 分钟。

题目链接：

题目意思：

给m个点，一个开始点和一个与水平方向的夹角。

求这条直线逆时针旋转时，第一个碰到的点a，然后以a点为新的转轴，再逆时针转，找到b，如此类推，最后顺序输出最开始的s个作为轴的点。

解题思路：

对于每一条旋转线，以轴为中心，分成两个相反向量，记为oa和ob.

对于每一个点c，如果该点在直线的左半部分，求出oa向量和oc向量的夹角，如果该点在直线的右半部分，求出ob向量与oc向量的夹角。

找出除去构成这条直线的两个点，找出其它的点的上述夹角最小的点，作为新的轴点，在构造出新的oa和ob.

注意oa和ob互为相反向量。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #define eps 1e-6#define INF 0x1f1f1f1f#define PI acos(-1.0)#define ll __int64#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;/*freopen("data.in","r",stdin);freopen("data.out","w",stdout);*/struct Point{ double x,y;}pp[22],p1,p2,p3;Point oa,ob; //两个向量double dis(Point a) //向量的长度{ return sqrt(a.x*a.x+a.y*a.y);}double dmult(Point a,Point b)//点积{ return a.x*b.x+a.y*b.y;}double xmult(Point a,Point b) //叉积{ return a.x*b.y-a.y*b.x;}int main(){ int t,d,m,s,be,aa; double an; scanf("%d",&t); while(t--) { scanf("%d%d%d%d%lf",&d,&m,&s,&be,&an); an=(an/180.0)*PI; //转化成弧度制 for(int i=1;i<=m;i++) scanf("%d%lf%lf",&aa,&pp[i].x,&pp[i].y); int la=be; //开始的点 oa.x=cos(an),oa.y=sin(an); //构造两个向量 ob.x=-oa.x,ob.y=-oa.y; int flag,find; double Max; printf("%d ",d); while(s--) { //cur=be; Max=-120; //printf("oa:%.1lf %.1lf ob:%.1lf %.1lf\n",oa.x,oa.y,ob.x,ob.y); for(int i=1;i<=m;i++) { if(i==be||i==la) //去掉构成直线的两点 continue; Point tmp; tmp.x=pp[i].x-pp[be].x; tmp.y=pp[i].y-pp[be].y; double tt=xmult(oa,tmp); if(tt>0) //在该直线的上方 { double t=dmult(oa,tmp)/dis(oa)/dis(tmp);//求oa和tmp的夹角 if(t>Max) //cos越大角度越小 { Max=t; flag=1; find=i; } } else if(tt<0) { double t=dmult(ob,tmp)/dis(ob)/dis(tmp); if(t>Max) { Max=t;flag=2;find=i; } } } printf("%d",find); // printf("") la=be; be=find; if(s) putchar(' '); else putchar('\n'); if(flag==1) //如果在上面的话 { ob.x=pp[la].x-pp[be].x; //它作为新的ob ob.y=pp[la].y-pp[be].y; oa.x=-ob.x; //互为相反向量 oa.y=-ob.y; } else { oa.x=pp[la].x-pp[be].x; oa.y=pp[la].y-pp[be].y; ob.x=-oa.x; ob.y=-oa.y; } } } return 0;}

转载于:https://www.cnblogs.com/bbsno1/p/3253850.html

你可能感兴趣的文章

成员函数对象类的const和非const成员函数的重载