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

京公网安备 11010502036488号