hdu 1245 Saving James Bond

点击打开链接hdu 1245

思路：最短路+floyd

分析：
1 题目讲的是有一个湖100x100这个人刚开始在一个直径为15的圆心在原点的园内，然后要通过跳跃的方式问我们他是否能够到达岸边。如果可以求出最短的路径和步数
2  很明确就是最短路问题。但是这个时候问题来了，起点和终点是在哪里，所以我们采用的是将原点作为起点，岸边做为终点。知道了起点和终点，我们就可以求最短路，但是这个时候会碰到另外一个问题，边的长度。对于这个问题，我们是采取的方法是将这些点分成三类。1类：起点  2类：终点  3类：其它点 ，那么我们就可以分别对这三类的点求出它和其它点的距离。

注意事项：
1 输入的数据中，点的范围可能会在园内或在湖外，所以在输入的时候要判断点是否合法。
2 这一题精度要求很严格，一些比较之类的要注意精度问题
3 注意n = 0 的情况，这里如果n = 0，但是d > 42.5 是可以跳出去的。但是只要有乌龟，这个人就必须通过踩在乌龟上面跳出去，所以n = 0是比较特殊的。
4  n不大所以什么方法都可以做
5 求所需几步的时候利用一个setp[][]数组，首先初始户为0然后将可以到达的点标记为1，最后只要在更新dis[][]的时候更新即可。

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF
#define eps 1e-12

int n;
double d;
double dis[MAXN][MAXN];
int setp[MAXN][MAXN];
struct Point{
   int x;
   int y;
}p[MAXN];

/*初始话边*/
void init(){
   memset(setp , 0 , sizeof(setp));/*初始话为0*/
   /*第三类的点*/
   for(int i = 2 ; i < n ; i++){
      for(int j = 2 ; j < n ; j++){
         double tmp_x = (p[i].x-p[j].x)*(p[i].x-p[j].x);
         double tmp_y = (p[i].y-p[j].y)*(p[i].y-p[j].y);
         double tmp = sqrt(tmp_x + tmp_y);
         if(tmp-d <= eps){
            dis[i][j] = tmp;
            setp[i][j] = 1;
         }
         else
            dis[i][j] = INF;
      }
      dis[i][i] = 0;
   }
   /*第一类点*/
   dis[1][1] = 0;
   dis[1][n] = dis[n][1] = INF;
   for(int i = 2 ; i < n ; i++){
      double tmp = sqrt((p[i].x)*(p[i].x)*1.0+(p[i].y)*(p[i].y)*1.0);
      if(tmp-7.5-d <= eps){/*注意要减去7.5*/
        dis[1][i] = dis[i][1] = tmp-7.5;
        setp[1][i] = setp[i][1] = 1;
      }
      else
        dis[1][i] = dis[i][1] = INF;
   }
   /*第二类点*/
   dis[n][n] = 0;
   for(int i = 2 ; i < n ; i++){
      int a = 50-abs(p[i].x);
      int b = 50-abs(p[i].y);
      int min = a < b ? a : b;
      if(min-d <= eps){
        dis[i][n] = dis[n][i] = min;
        setp[i][n] = setp[n][i] = 1;
      }
      else
        dis[i][n] = dis[n][i] = INF;
   }
}

/*floyd算法*/
void floyd(){
   for(int k = 1 ; k <= n ; k++){
      for(int i = 1 ; i <= n ; i++){
         for(int j = 1 ; j <= n ; j++){
            if(dis[i][j]-(dis[i][k]+dis[k][j]) >= eps){
              dis[i][j] = dis[i][k]+dis[k][j];
              setp[i][j] = setp[i][k] + setp[k][j];/*更新数组*/
            }
         }
      }
   }
}

int main(){
   int a , b , j;
   while(scanf("%d %lf" , &n , &d) != EOF){
       j = 2;/*默认1为起点，j从2开始*/
       for(int i = 0 ; i < n ; i++){
          scanf("%d%d" , &a , &b);
          if(abs(a) < 8 && abs(b) < 8 || abs(a) > 50 && abs(b) > 50)/*如果不合法就跳过*/
            continue;
          p[j].x = a;
          p[j++].y = b;
       }
       n = j;
       if(!n){/*判断n是否为0*/
          if(d-42.5 >= eps)
            printf("42.50 1\n");
          else
            printf("can't be saved\n");
          continue;
       }
       init();
       floyd();
       if(dis[1][n] != INF)/*是否可以跳出去*/
         printf("%0.2lf %d\n" , dis[1][n] , setp[1][n]);
       else
         printf("can't be saved\n");
   }
   return 0;
}