New Game! （最短路+建图）

时间：2022-05-12 09:15:46

New Game!

https://www.nowcoder.com/acm/contest/201/L

题目描述

Eagle Jump公司正在开发一款新的游戏。Hifumi Takimoto作为其中的员工，获得了提前试玩的机会。现在她正在试图通过一个迷宫。
这个迷宫有一些特点。为了方便描述，我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线 L1:Ax+By+C1=0, L2:Ax+By+C2=0，还有 n 个圆 New Game! （最短路+建图）。角色在直线上、圆上、园内行走不消耗体力。在其他位置上由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)，其中 A,B 不同时为 0。
接下来 n 行每行三个整数 x,y,r(-10000 ≤ x,y ≤ 10000, 1≤ r ≤ 10000) 表示一个圆心为 (x,y)，半径为 r 的圆。

输出描述:

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

-4

 即算正确。

输入

2 0 1 0 -4

0 1 1

1 3 1

输出

0.236068

可以把圆看成一个点，利用点到直线的距离公式和点到点的距离公式，求出各个点之间的距离，跑一遍最短路即可
 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<stack>

 #include<algorithm>

 #include<cmath>

 #define PI acos(-1.0)

 #define INF 0x3f3f3f3f

 using namespace std;

 int n;

 double A,B,C1,C2;

 struct Circle{

     double x,y,r;

 }p[];

 double map[][];

 double vis[];

 double dis[];

 double dist1(Circle a,Circle b){

     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))-a.r-b.r;

 }

 double dist2(double a,double b,double c,Circle d){

     return (fabs(a*d.x+b*d.y+c)/sqrt(a*a+b*b)-d.r);

 }

 void Dijstra(){

     for(int i=;i<=n+;i++){

         dis[i]=map[][i];

         vis[i]=;

     }

     vis[]=;

     dis[]=;

     for(int i=;i<n+;i++){

         double minn=INF;

         int pos=;

         for(int j=;j<=n+;j++){

             if(!vis[j]&&dis[j]<minn){

                 minn=dis[j];

                 pos=j;

             }

         }

         vis[pos]=;

         for(int j=;j<=n+;j++){

             if(!vis[j]&&dis[j]>minn+map[pos][j]){

                 dis[j]=minn+map[pos][j];

             }

         }

     }

     cout<<dis[n+]<<endl;

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n>>A>>B>>C1>>C2;

     for(int i=;i<;i++){

         for(int j=;j<;j++){

             map[i][j]=INF;

         }

     }

     for(int i=;i<=n+;i++){

         cin>>p[i].x>>p[i].y>>p[i].r;

     }

     double tmp;

     for(int i=;i<=n+;i++){

         for(int j=i+;j<=n+;j++){

             tmp=dist1(p[i],p[j]);

             if(tmp>)

                 map[i][j]=map[j][i]=tmp;

             else

                 map[i][j]=map[j][i]=;

         }

     }

     for(int i=;i<=n+;i++){

         tmp=dist2(A,B,C1,p[i]);

         if(tmp>)

             map[][i]=map[i][]=tmp;

         else

             map[][i]=map[i][]=;

         tmp=dist2(A,B,C2,p[i]);

         if(tmp>)

             map[n+][i]=map[i][n+]=tmp;

         else

             map[n+][i]=map[i][n+]=;

     }

     map[][n+]=map[n+][]=fabs(C1-C2)/sqrt(A*A+B*B);

     Dijstra();

 }

相关文章