T1
设点 \(i\) 直接收到点 \(j\) 信号的最小代价为 \(\sqrt{x}\)，由两圆相切的条件可知：
\[\sqrt{(x_i-x_j)^2+(x-r_j)^2}=x+r_j\\
(x_i-x_j)^2+(x-r_j)^2=(x+r_j)^2\\
(x_i-x_j)^2=4xr_j\\
x=\dfrac{(x_i-x_j)^2}{4r_j}\\
\]
DP，设 \(f_i\) 为基站 \(i\) 收到信号的最小代价。
转移式：
\[f_i=\min_{j=1}^i (f_j+\sqrt{\frac{(x_i-x_j)^2}{4r_j}})+v_i\\
=\min_{j=1}^i (f_j+\frac{x_i-x_j}{2\sqrt{r_j}})+v_i\\
=\min_{j=1}^i (\frac{x_i}{2\sqrt{r_j}}+f_j-\frac{x_j}{2\sqrt{r_j}})+v_i\\
\]
将 \(\min\) 里面的式子实际上是斜率为 \(\dfrac{1}{2\sqrt{r_j}}\)，截距为 \(f_j-\dfrac{x_j}{2\sqrt{r_j}}\) 在 \(x=x_i\) 处的值。
可以使用李超线段树优化，由于值域较大要动态开点，时间复杂度 \(\mathcal O(n\log n)\)：
#include<bits/stdc++.h>
#define N 500005
using namespace std;
using db=double;
using ll=long long;
ll m,p[N];
int n,k,v[N],r[N];
db f[N],ans=INFINITY;
class SGT{#define v(i) tr[i].val#define l(i) tr[i].lch#define r(i) tr[i].rchprivate:struct Seg{db a,b;db get(int x){return a*x+b;}};struct node{Seg val;int lch,rch;node(){val={0,INFINITY},lch=rch=0;}}tr[N*20];int rt,idx;static bool cmp(Seg x,Seg y,int k){return x.get(k)>y.get(k);}void ins(Seg k,int &x,ll l=0,ll r=1e12){if(!x) x=++idx;int mid=l+r>>1;if(cmp(v(x),k,mid)) swap(v(x),k);if(l==r) return;if(cmp(v(x),k,l)) ins(k,l(x),l,mid);if(cmp(v(x),k,r)) ins(k,r(x),mid+1,r);}db query(int p,int &x,ll l=0,ll r=1e12){if(!x) return INFINITY;if(l==r) return v(x).get(p);int mid=l+r>>1;if(p<=mid) return min(v(x).get(p),query(p,l(x),l,mid));return min(v(x).get(p),query(p,r(x),mid+1,r));}public:void ins(Seg x){ins(x,rt);}db query(ll x){return query(x,rt);}#undef v#undef l#undef r
}tr;
int main(){scanf("%d%lld",&n,&m);for(int i=1;i<=n;i++) scanf("%lld%d%d",p+i,r+i,v+i);tr.ins({0.5/sqrt(r[1]),(f[1]=v[1])-p[1]/(2*sqrt(r[1]))});for(int i=2;i<=n;i++)f[i]=tr.query(p[i])+v[i],tr.ins({0.5/sqrt(r[i]),f[i]-p[i]/(2*sqrt(r[i]))});for(int i=1;i<=n;i++) if(p[i]+r[i]>=m) ans=min(ans,f[i]);printf("%.3f",ans);return 0;
}