题目中情况要么从边界传送,要么直接直接过去。那么就是要求出从边界传送的最短路,由于边界传送的特点,在圆周上是一个凹的函数图形,所以使用三分去求解即可。
那么问题就到了如何定三分的左右边界呢?在园的方程里面有一个参数方程。在里面可以从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;
}