``````int px(O pa, O pb)
{
if(a*pa.x+b*pa.y+c1<0&&a*pb.x+b*pb.y+c1<0)//都在L1左边，按照距离L1的距离从大到小
return pa.s<pb.s;
else if(a*pa.x+b*pa.y+c1>0&&a*pb.x+b*pb.y+c1>0)//都在L1右边，按照距离L1的距离从小到大
return pa.s>pb.s;
else
return a*pa.x+b*pa.y+c1<a*pb.x+b*pb.y+c1?0:1;//一左一右，左在右前
}
``````

dp[i].s=min(dp[j].s，d[i].s), j<i。

``````for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
//d(ij)如图的黄色虚线距离。
dp[j].s=(dp[i].s, d(ij));
}
}
``````

``````#include<bits/stdc++.h>
using namespace std;

struct O
{
double x;
double y;
double r;
double s;
};
O w[1005];
long long n, a, b, c1, c2;

int px(O pa, O pb)
{
if(a*pa.x+b*pa.y+c1<0&&a*pb.x+b*pb.y+c1<0)
return pa.s<pb.s;
else if(a*pa.x+b*pa.y+c1>0&&a*pb.x+b*pb.y+c1>0)
return pa.s>pb.s;
else
return a*pa.x+b*pa.y+c1<a*pb.x+b*pb.y+c1?0:1;
}
int px1(O pa, O pb)
{
return pa.s<pb.s;
}
int main()
{
scanf("%lld%lld%lld%lld%lld",&n, &a, &b, &c1, &c2);
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf",&w[i].x, &w[i].y, &w[i].r);

};

if(c1>c2)
swap(c1, c2);

for(int i=0;i<n;i++)//初始化
{
double fz=fabs(a*w[i].x+b*w[i].y+c1);
double fm=sqrt(a*a+b*b);
double f1=fz/fm;
if(f1<=w[i].r)
w[i].s=0;
else
w[i].s=f1-w[i].r;
}
sort(w,w+n, px);//圆的排序

for(int i=0;i<n;i++)//dp递推
{
for(int j=i+1;j<n;j++)
{

double s1=sqrt((w[i].x-w[j].x)*(w[i].x-w[j].x)+(w[i].y-w[j].y)*(w[i].y-w[j].y));
double s2=w[i].r+w[j].r;
if(s1>s2)
w[j].s=min(w[i].s+s1-s2, w[j].s);
else
w[j].s=min(w[i].s, w[j].s);
}
}
for(int i=0;i<n;i++)//加上到L2的距离
{
double fz=fabs(a*w[i].x+b*w[i].y+c2);
double fm=sqrt(a*a+b*b);
double f1=fz/fm;
if(f1<=w[i].r)
w[i].s+=0;
else
w[i].s+=f1-w[i].r;
}
sort(w,w+n, px1);//按s从小到大排序
printf("%.6f\n",w[0].s);

return 0;
}

``````