题目:青蛙一次只能跳一个单位距离,从圆一点到另一点。最小步数是多少,路径的所有点都不能通过?
解法 旋转到a的角度为0,这样b只会在0-180度浮动,然后可以根据情况进行讨论
1.a=b 此时步数为0
2.b-a<=90只需要构造圆外等腰三角形 步数为2 顶点坐标根据等腰三角形三点一线推得(xa xb,ya yb);
3.步数3和步数4 不难发现a和b切线的两点距离小于等于1和大于1,这个角度可以写一个程序来运行,是的b-a<=131时为3,>131为4
步数3时P的坐标可以根据剩余细节来解决M,与∠得出
#include <bits/stdc .h> using namespace std; double pi=acos(-1.0); struct point{ double x,y; point(double x0=0,double y0=0):x(x0),y(y0){} }; point rotate(double x,double y,double jiao){ jiao=jiao*pi/180.0; return point(x*cos(jiao)-y*sin(jiao),x*sin(jiao) y*cos(jiao)); } void solve(int sign,double a,double b){ double aa=a;double bb=b; if(!sign){ if(b-a<=90){ double nx=cos(a*pi/180.0) cos(b*pi/180.0); double ny=sin(a*pi/180.0) sin(b*pi/180.0); printf("2\n%.10f %.10f\n",cos(a*pi/180.0),sin(a*pi/180.0)); printf("%.10f %.10f\n",nx,ny); printf("%.10f %.10f\n",cos(b*pi/180.0),sin(b*pi/180.0)); return ; } double minx=a; a=0;b=b-minx; if(b<=131){ printf("3\n%.10f %.10f\n",cos(aa*pi/180.0),sin(aa*pi/180.0)); double nx=1.0;double ny=1.0;point t; t=rotate(nx,ny,minx); printf("%.10f %.10f\n",t.x,t.y); double lx=cos(b*pi/180.0);double ly=sin(b*pi/180.0); double tem=(1.0-cos(b*pi/180.0))*(1.0-cos(b*pi/180.0)) (1.0-sin(b*pi/180.0))*(1.0-sin(b*pi/180.0));double len=sqrt(1.0-tem/4.0); double ang=atan2((1.0-sin(b*pi/180.0)),(1.0-cos(b*pi/180.0))); double mx=(1.0 cos(b*pi/180.0))/2.0;double my=(1.0 sin(b*pi/180.0))/2.0; mx=mx-len*sin(ang);my=my len*cos(ang); t=rotate(mx,my,minx); printf("%.10f %.10f\n",t.x,t.y); printf("%.10f %.10f\n",cos(bb*pi/180.0),sin(bb*pi/180.0)); }else{ printf("4\n%.10f %.10f\n",cos(aa*pi/180.0),sin(aa*pi/180.0));point t; t=rotate(1.0,1.0,minx); printf("%.10f %.10f\n",t.x,t.y); t=rotate(0.0,1.0,minx); printf("%.10f %.10f\n",t.x,t.y); double nx=cos(b*pi/180.0);double ny=1.0 sin(b*pi/180.0); t=rotate(nx,ny,minx); // printf("minx=%.10f ",minx); printf("%.10f %.10f\n",t.x,t.y); printf("%.10f %.10f\n",cos(bb*pi/180.0),sin(bb*pi/180.0)); } } if(sign){ if(b-a<=90){ double nx=cos(a*pi/180.0) cos(b*pi/180.0); double ny=sin(a*pi/180.0) sin(b*pi/180.0); printf("2\n%.10f %.10f\n",cos(b*pi/180.0),sin(b*pi/180.0)); printf("%.10f %.10f\n",nx,ny); printf("%.10f %.10f\n",cos(a*pi/180.0),sin(a*pi/180.0)); return ; } double minx=a; a=0;b=b-minx; if(b<=131){ printf("3\n%.10f %.10f\n",cos(bb*pi/180.0),sin(bb*pi/180.0)); double nx=1.0;double ny=1.0;point t; double lx=cos(b*pi/180.0);double ly=sin(b*pi/180.0); double tem=(1.0-cos(b*pi/180.0))*(1.0-cos(b*pi/180.0)) (1.0-sin(b*pi/180.0))*(1.0-sin(b*pi/180.0));double len=sqrt(1.0-tem/4.0); double ang=atan2((1.0-sin(b*pi/180.0)),(1.0-cos(b*pi/180.0))); double mx=(1.0 cos(b*pi/180.0))/2.0;double my=(1.0 sin(b*pi/180.0))/2.0; mx=mx-len*sin(ang);my=my len*cos(ang); t=rotate(mx,my,minx); printf("%.10f %.10f\n",t.x,t.y); t=rotate(1.0,1.0,minx); printf("%.10f %.10f\n",t.x,t.y); printf("%.10f %.10f\n",cos(aa*pi/180.0),sin(aa*pi/180.0)); }else{ printf("4\n%.10f %.10f\n",cos(bb*pi/180.0),sin(bb*pi/180.0));point t; double nx=cos(b*pi/180.0);double ny=1.0 sin(b*pi/180.0); t=rotate(nx,ny,minx); printf("%.10f %.10f\n",t.x,t.y); t=rotate(0.0,1.0,minx); printf("%.10f %.10f\n",t.x,t.y); t=rotate(1.0,1.0,minx); printf("%.10f %.10f\n",t.x,t.y); printf("%.10f %.10f\n",cos(aa*pi/180.0),sin(aa*pi/180.0)); } } } int main() { int t; cin>>t; while(t--){ double a,b; cin>>a>>b; if(a==b){ printf("0\n%.10f %.10f\n",cos(a*pi/180.0),sin(a*pi/180.0)); continue; }double aa=a;double bb=b; if(b>a&&(b-a)<=180){ solve(0,a,b); } if(b>a&&b-a>180){ solve(1,b,a 360); } if(a>b&&(a-b)<=180){ solve(1,b,a); } if(a>b&&(a-b)>180){ solve(0,a,b 360); } } }