只要用时间 t 的公式对 k 求导数,一切都会好起来的
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e5+5;
// 定义结构体D,用于存储二维平面上点的横、纵坐标
struct D{
double x; // 点的横坐标
double y; // 点的纵坐标
};
// 定义数组存储所有点的坐标
D d[N];
int main(){
// 优化输入输出流,提升cin/cout的速度,适配大数据量输入
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n; // 存储点的总数
cin>>n;
double ans=0; // 存储最终结果的累加变量,初始化为0
// 输入第一个点的坐标
cin>>d[1].x>>d[1].y;
// 遍历从第2个点到第n个点,逐个处理相邻两点的计算逻辑
for(ll i=2;i<=n;i++){
// 输入当前第i个点的坐标
cin>>d[i].x>>d[i].y;
// 计算当前点与前一个点(i-1)之间的欧几里得距离e
double e=sqrt(pow(d[i].x-d[i-1].x,2)+pow(d[i].y-d[i-1].y,2));
// 计算tmp值,作为后续二分查找的目标阈值
double tmp=-1/(e*log(0.5));
// 初始化二分查找的左右边界:l为下界0,r为上界1e9+7(覆盖所有可能的解范围)
double l=0,r=1e9+7;
// 二分查找迭代100次,通过不断缩小区间逼近方程的解
for(ll j=1;j<=100;j++){
// 取当前区间的中点m
double m=(l+r)/2;
// 判断中点是否满足条件,调整二分区间
// 核心逻辑:寻找满足0.5^m <= tmp的最小r,通过二分缩小区间
if(pow(0.5,m)<=tmp){
r=m; // 解在左半区间,收缩右边界
}else{
l=m; // 解在右半区间,收缩左边界
}
}
// 累加当前相邻两点对最终结果的贡献值到ans中
ans+=2*r+2*e*pow(0.5,r);
}
// 输出最终结果,保留9位小数
printf("%.9lf",ans);
return 0;
}

京公网安备 11010502036488号