题目中情况要么从边界传送,要么直接直接过去。那么就是要求出从边界传送的最短路,由于边界传送的特点,在圆周上是一个凹的函数图形,所以使用三分去求解即可。
那么问题就到了如何定三分的左右边界呢?在园的方程里面有一个参数方程。在里面可以从0,2*PI的范围内将圆表示出来。所以通过参数方程即可求解。
#include <bits/stdc++.h> using namespace std; struct Node{ double x; double y; } daxiang, target; double R; double dist(double x, double y, double x1, double y1) { return sqrt(pow(x-x1,2)+pow(y-y1,2)); } double total_dist(double m) { double x = R*cos(m); double y = R*sin(m); //开始计算距离。 double len = dist(x,y,daxiang.x,daxiang.y)+dist(-x, -y, target.x, target.y); return len; } int main() { cin>>R; cin>>daxiang.x>>daxiang.y; cin>>target.x>>target.y; double l = 0, r = acos(-1)*2.0; double ans = 0; //直接固定次数,以防止精度问题出现死循环。 for (int i=0;i<1000;i++) { double m1 = l+(r-l)/3; double m2 = r-(r-l)/3; // cout<<m1<<" "<<m2<<endl; // cout<<"ans = "<<ans<<endl; if (total_dist(m1)<=total_dist(m2)) { ans = total_dist(m1); r = m2; }else { ans = total_dist(m2); l = m1; } } // cout<<"ans = "<<ans<<endl; ans = min(ans, dist(daxiang.x, daxiang.y, target.x, target.y)); printf("%.12lf", ans); return 0; }