牛客国庆集训派对Day1L题NewGame

链接:New Game

来源：牛客网

Eagle Jump公司正在开发一款新的游戏。Hifumi Takimoto作为其中的员工，获得了提前试玩的机会。现在她正在试图通过一个迷宫。
这个迷宫有一些特点。为了方便描述，我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线 L1:Ax+By+C1=0, L2:Ax+By+C2=0，还有 n 个圆。角色在直线上、圆上、园内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。

Hifumi Takimoto想从 L1出发，走到 L2。请计算最少需要多少体力。

输入描述:

第一行五个正整数 n,A,B,C1,C2(1≤ n ≤ 1000, -10000 ≤ A,B,C1,C2≤ 10000)，其中 A,B 不同时为 0。

接下来 n 行每行三个整数 x,y,r(-10000 ≤ x,y ≤ 10000, 1≤ r ≤ 10000) 表示一个圆心为 (x,y)，半径为 r 的圆。

输出描述:

仅一行一个实数表示答案。与正确结果的绝对误差或者相对误差不超过 10-4即算正确。

#include<iostream>
//#include<stdio.h>
//#include<string>
//#include <functional>
#include<algorithm>
//#include<iomanip>
#include<vector>
using namespace std;
double n, a, b, c1, c2;
struct Node {
    Node(double pointx, double pointy, double pointr) {
        x = pointx, y =pointy, r = pointr;
        d = max(abs(a*x + b * y + c1) / sqrt(a*a + b * b)-r,0.0);
    }
    Node(istream &m)
    {
        cin >> x >> y >> r;
        d = max(abs(a*x + b * y + c1) / sqrt(a*a + b * b) - r, 0.0);
    }
    double  x, y, r;
    double d;
};
double  ans[2000];
bool cmp(const Node &m, const Node &n)
{
    return m.d < n.d;
}
double c2c(const Node &a, const Node &b)
{
    double m = max(sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)) - a.r - b.r, 0.0);
    return m;
}
double c2l(const Node &circle)
{
    return max(abs(a*circle.x + b * circle.y + c2) / sqrt(a*a + b * b) - circle.r, 0.0);
}
vector<Node>  all;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> a >> b >> c1 >> c2;
    for (int i = 0; i < n; ++i)
    {
        all.push_back(Node(cin));
    }
    sort(all.begin(), all.end(), [](const Node&a, const Node &b){ return a.d < b.d; });
    int size = all.size();
    for (int i = 0; i < size; ++i)
    {
        ans[i] = all[i].d;
        for (int j = 0; j < i; ++j)
        {
            ans[i] = min(ans[i], ans[j] + c2c(all[i], all[j]));
        }
    }
    double ansdouble = 100000000;
    for (int i = 0; i < size; ++i)
    {
        ansdouble = min(ansdouble, ans[i] + c2l(all[i]));
    }
    cout << ansdouble << endl;
    return 0;
}