牛客国庆集训派对Day1 L New Game!——————建图+

比眉伴天荒 2022-05-09 05:18 140阅读 0赞

链接：[https://www.nowcoder.com/acm/contest/201/L][https_www.nowcoder.com_acm_contest_201_L]  
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒  
空间限制：C/C++ 1048576K，其他语言2097152K  
Special Judge, 64bit IO Format: %lld  
**题目描述**  
Eagle Jump公司正在开发一款新的游戏。Hifumi Takimoto作为其中的员工，获得了提前试玩的机会。现在她正在试图通过一个迷宫。  
这个迷宫有一些特点。为了方便描述，我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线  L 1 : A x + B y + C 1 = 0 , L 2 : A x + B y + C 2 = 0 L1:Ax+By+C1=0, L2:Ax+By+C2=0 L1:Ax\+By\+C1=0,L2:Ax\+By\+C2=0，还有 n 个圆 C i : ( x − x i ) 2 + ( y − y i ) 2 = r i 2 \\large C\_i:(x-x\_i)^2+(y-y\_i)^2=r\_i^2 Ci:(x−xi)2\+(y−yi)2=ri2 。角色在直线上、圆上、园内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。  
Hifumi Takimoto想从 L1 出发，走到 L2 。请计算最少需要多少体力。  
**输入描述:**  
第一行五个正整数  n , A , B , C 1 , C 2 ( 1 ≤ n ≤ 1000 , − 10000 ≤ A , B , C 1 , C 2 ≤ 10000 ) n,A,B,C1,C2 (1≤ n ≤ 1000, -10000 ≤ A,B,C1,C2 ≤ 10000) 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(-10000 ≤ x,y ≤ 10000, 1≤ r ≤ 10000) x,y,r(−10000≤x,y≤10000,1≤r≤10000) 表示一个圆心为 ( x , y ) (x,y) (x,y)，半径为  r r r的圆。  
**输出描述:**  
仅一行一个实数表示答案。与正确结果的绝对误差或者相对误差不超过 10-4 即算正确。  
示例1  
**输入**  
2 0 1 0 -4  
0 1 1  
1 3 1  
**输出**  
0.236068

--------------------

在 L 1 L\_1 L1上找出起点  
在 L 2 L\_2 L2上找出终点  
让这个人从 L 1 L\_1 L1走到 L 2 L\_2 L2消耗的体力是最少的  
在直线上和在圆上行走不消耗体力  
所以，我们可以建图

在  L 1 L\_1 L1 上抽象出来一个超级起点，  
在  L 2 L\_2 L2 上抽象出来一个超级终点

粘代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef pair<double , int> P;
    
    const int MAXN = 2e3+4;
    const double INF = 1e9;
    int n;
    struct node{
        
            int to;
            double cost;
            node(){
        };
            node(int _to,double _cost)
            {
        
                    to=_to; cost=_cost;
            }
    };
    vector<node> a[MAXN];
    double x[MAXN],y[MAXN],r[MAXN];
    double A,B,C1,C2;
    double d[MAXN];
    double dis0(double x1,double y1,double x2,double y2)//两个圆心之间的距离
    {
        
            return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    double dis1(double x,double y)//点到直线L1的距离
    {
        
            return fabs(A*x+B*y+C1)/sqrt(A*A+B*B);
    }
    
    double dis2(double x,double y)//点到直线L2的距离
    {
        
            return fabs(A*x+B*y+C2)/sqrt(A*A+B*B);
    }
    
    double dijkstra(int s)
    {
        
            priority_queue<P,vector<P>,greater<P> >que;
            que.push(P(0,s));
            d[s]=0;
            while(que.size())
            {
        
                    P p=que.top();que.pop();
                    int v=p.second;
                    if(d[v]<p.first) continue;
                    for(int i=0;i<a[v].size();i++)
                    {
        
                            node e=a[v][i];
                            if(d[e.to] > d[v]+e.cost)
                            {
        
                                    d[e.to] = d[v] + e.cost;
                                    que.push(P(d[e.to],e.to));
                            }
                    }
            }
            return d[n+1];
    }
    
    int main()
    {
        
            scanf("%d %lf %lf %lf %lf",&n,&A,&B,&C1,&C2);
            for(int i=1;i<=n;i++)
                    scanf("%lf %lf %lf",&x[i],&y[i],&r[i]);
            for(int i=0;i<=n+1;i++)
            {
        
                    d[i] = INF;
    //                printf("%f\n",d[i]);
            }
    
            for(int i=1;i<=n;i++)//建立超级原点,在直线L1上
                    if(dis1(x[i],y[i])>r[i])
                            a[0].push_back(node(i,dis1(x[i],y[i])-r[i]));
                    else
                            a[0].push_back(node(i,0));
            for(int i=1;i<=n;i++)//建立超级终点,在直线L2上
                    if(dis2(x[i],y[i])>r[i])
                            a[i].push_back(node(n+1,dis2(x[i],y[i])-r[i]));
                    else
                            a[i].push_back(node(n+1,0));
            for(int i=1;i<=n;i++)
                    for(int j=i+1;j<=n;j++)
                    {
        
                            if(dis0(x[i],y[i],x[j],y[j])>r[i]+r[j])
                            {
        
                                    a[i].push_back(node(j,dis0(x[i],y[i],x[j],y[j])-r[i]-r[j]));
                                    a[j].push_back(node(i,dis0(x[i],y[i],x[j],y[j])-r[i]-r[j]));
                            }
                            else
                            {
        
                                    a[i].push_back(node(j,0));
                                    a[j].push_back(node(i,0));
                            }
                    }
            double ans=dijkstra(0);
            printf("%f\n",min(ans,fabs(C1-C2)/sqrt(A*A+B*B)));
            return 0;
    }

[https_www.nowcoder.com_acm_contest_201_L]: https://www.nowcoder.com/acm/contest/201/L