玲珑杯 round 11G题目解答:人的位置在(x1,y1),速率为v(方向任意可变),龙卷风的位置为(x0,y0),速度为(vx,vy),问你人能不能追上龙卷风。
解题思路:这道题坑点比较多,比赛时没有做出来,要考虑人的位置与龙卷风的位置重合了没有,还要考虑二者速度为零的情况,还要考虑人开始就在龙卷风运动的轨迹上,这些特殊情况考虑了之后,一般情况的做法就是先比较二者的速度大小,如果人的速度大,一定能追上,如果相等,那么当人的初始位置与龙卷风的初始位置直接的连线与龙卷风速度的方向形成锐角这时人可以追上,否则不能,若人的速度小于龙卷风的速度,则假设人可以追上,形成一个三角形,设追上时所用时间为t,根据余玄定理列出方程,只含有一个未知数t,列出的方程是个一元二次方程,开口向上,对称轴恒在x轴正半轴,所以,当这个方程的根的判别式大于等于0时,t恒有正数解,这时人可以追上,否则不能。
#includeusing namespace std; int x,y; int x2,y2; int v; int vx,vy; double eps = 1e-10; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&x,&y); scanf("%d%d",&x2,&y2); scanf("%d%d",&vx,&vy); scanf("%d",&v); double d = sqrt((double)(x2 - x)*(x2 - x) + (double)(y2 - y)*(y2 - y)); if(x == x2&&y == y2)//重合 { printf("YES\n"); continue; } if(vx == 0&&vy == 0)//静止 { if(v == 0) printf("NO\n"); else printf("YES\n"); } else if(v == 0) { if(vx == 0) { if(x == x2&&y <= y2) printf("YES\n"); else printf("NO\n"); } else if(vy == 0) { if(y == y2&&x <= x2) printf("YES\n"); else printf("NO\n"); } else { double k = (double)vy/(double)vx; double yy = k*x2 - k*x + y; if(fabs(yy - (double)y2) <= eps&&y2 >= y) printf("YES\n"); else printf("NO\n"); } } else if(vx == 0)//k 不存在 { if(v > vy) printf("YES\n"); else if(v == vy) { if(y2 > y) printf("YES\n"); else printf("NO\n"); } else { if(y2 <= y) printf("NO\n"); else { double m = (double)abs(y2 - y)/d; if((double)v*v - (1 - m*m)*vy*vy >= eps) printf("YES\n"); else printf("NO\n"); } } } else if(vy == 0)//k == 0 { if(v > vx) { printf("YES\n"); } else if(v == vx) { if(x2 > x) printf("YES\n"); else printf("NO\n"); } else { if(x2 <= x) printf("NO\n"); else { double m = double(x2 - x)/d; if((double)v*v - (1 - m*m)*vx*vx >= eps) printf("YES\n"); else printf("NO\n"); } } } else//k存在,且不为零 { double v1 = sqrt((double)vx*vx + (double)vy*vy); double v2 = (double)v; if(v2 - v1 > eps) printf("YES\n"); else if(fabs(v2 - v1) < eps) { double k1 = (double)vy/(double)vx; double k2 = -1/k1; double _x = (k1*x - k2*x2 + y2 - y)/(k1 - k2); double _y = k1*_x + y - k1*x; double d2 = sqrt((x - _x)*(x - _x) + (y - _y)*(y - _y)); if(_y - y > eps) printf("YES\n"); else printf("NO\n"); } else { double k1 = (double)vy/(double)vx; double k2 = -1/k1; double _x = (k1*x - k2*x2 + y2 - y)/(k1 - k2); double _x0 = (double)x; if(_x - _x0 <= eps) printf("NO\n"); else { double _y = k1*_x + y - k1*x; //double d1 = sqrt((x2 - _x)*(x2 - _x) + (y2 - _y)*(y2 - _y)); double d2 = sqrt((x - _x)*(x - _x) + (y - _y)*(y - _y)); double m = d2/d; if(v2*v2 - (1 - m*m)*v1*v1 >= eps) printf("YES\n"); else printf("NO\n"); } } } } return 0; }