The 2019 ACM-ICPC China Shannxi Provincial Programming Contest C.Angel's Journey

本文主要是介绍The 2019 ACM-ICPC China Shannxi Provincial Programming Contest C.Angel's Journey，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

T(T<=500)组样例，每组样例给出rx,ry,r,x,y(-100<=rx,ry,x,y<=100,0<r<=100)

代表被救的人在(rx,ry-r)位置，且(rx,ry)为圆心有一个半径为r的圆

你从圆外(x,y)出发，题目保证y>ry，

y=ry及这条水平线以下的圆外部分是海，圆内部也是海，都不能经过

问(x,y)到(rx,ry-r)的最短距离

分析：有关切线的问题一定要往三角形上面靠，这样就简单多了。

记A(x,y)，O(rx,ry)，S(rx,ry-r)，D(rx+r,ry)，E(rx-r,ry)

过A的直线与圆的切点F，坐标未知

考虑棕色边的三角形AOS，余弦定理求顶角AOS，

余弦定理求直角三角形AFO的角AOF，作差得角FOS

①角FOS小于90度，说明FOS在海里，不可通过直线达，取点E和点D的较近点，再走1/4弧

②角FOS大于90度，FOS可以通过与切点的线段到达，再走圆上一段弧即可

这种判断，省去了对两个切点的分别判断

参考博客：https://blog.csdn.net/code92007/article/details/90582566

代码：

#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
int t,rx,ry,r,x,y;int dis(int x,int y,int i,int j) {return (x-i)*(x-i)+(y-j)*(y-j);
}int main() {while(~scanf("%d",&t)) {while(t--) {scanf("%d%d%d%d%d",&rx,&ry,&r,&x,&y);int d1=dis(rx,ry,x,y),d2=dis(rx,ry-r,x,y);double ag1=acos(1.0*(d1+r*r-d2)/(2.0*r*sqrt(d1)));double ag2=acos(1.0*r/sqrt(d1));double ag3=ag1-ag2;if(ag3<=pi/2) {double s=pi/2*r;if(x>rx) s+=sqrt(dis(x,y,rx+r,ry));else s+=sqrt(dis(x,y,rx-r,ry));printf("%.4f\n",s);}else {printf("%.4f\n",ag3*r+sqrt(d1-r*r));}}}return 0;
}

 

这篇关于The 2019 ACM-ICPC China Shannxi Provincial Programming Contest C.Angel's Journey的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---