题目链接：https://www.nowcoder.com/acm/contest/201/L
题目大意：给你n个圆和两条直线，在圆上，和圆内和直线上行走不消耗体力。
在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。Hifumi Takimoto想从 L1 出发，走到 L2 。请计算最少需要多少体力。

思路：因为圆与直线的位置可以任意。从L1到L2，我们计算从c大的直线的到c小的直线距离就好了，如图L1->L2。
其实思路就是dp最短路。我们先按照圆与L1的距离排序。（排序依据不只是距离，因为可能在直线外）

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为初始到L1的距离）
dp[i].s=min(dp[j].s，d[i].s), j<i。
因为n<=1000;直接两种循环暴力。
先初始化s[i].s=d。

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));
    }
}

这样求出所有圆到L1的距离，在加上该圆的到L2的距离。
再求dp[i].s的最小距离就行了。

思考：这题当时写了两个小时，因为犯了不少错误。最后AC的瞬间，高兴跳起来的欢呼。这可能就是ACM的魅力吧！。

#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;
}