B - 娜娜梦游仙境系列——跳远女王

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

娜娜觉得钢琴很无趣了，就抛弃了钢琴，继续往前走，前面是一片湖，娜娜想到湖的对岸，可惜娜娜找了好久都没找到小桥和小船，娜娜也发现自己不是神仙，不能像八仙过海一样。正当娜娜发愁的时候，娜娜发现湖上面有一些石头！娜娜灵机一动，发现可以沿着石头跳吖跳吖，这样一直跳下去，或许能跳到对岸！

娜娜把所有石头的位置都告诉你，然后娜娜能跳的最远距离也是知道的~请聪明的你告诉娜娜，她能够顺利到达对岸吗？

为了能够顺利的表达每个石头的位置，假设娜娜正在x轴上，表示湖的一岸，湖的另一岸是直线y=y0，湖中的石头都以有序二元组<x,y>表示，我们可以假设湖是无穷宽，两个石头的距离为几何距离，石头与岸的距离为点到直线的距离。

Input

多组数据，首先是一个正整数t(t<=20)表示数据组数

对于每组数据首先是三个整数y0(1<=y0<=1000),n(0<=n<=1000),d(0<=d<=1000)，分别表示湖的另一岸的位置、石头的个数、娜娜一次最远能跳的距离。

接下来是n行，每行是两个整数x,y（0<=|x|<=1000,0<y<y0）

Output

对于每组数据，如果娜娜能够到达湖的另一岸，先输出“YES”，再输出一个整数，表示娜娜最少要跳多少次才能到达另一岸，

如果娜娜不能到达湖的另一岸，先输出“NO”，再输出一个整数，表示娜娜距离湖的另一岸最近的距离。(注意大小写)

Sample Input

Sample Output

YES

4

NO

3

Hint

样例一，从x轴->(0,1)->(0,2)->(0,3)->对岸，总共跳4步，输出4

样例二，从x轴->(0,1)->(1,2)->(2,3)，此时距离对岸的距离为3，最大跳跃距离为2，无法到达对岸，故输出3

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <list>

 #include <iomanip>

 #include <cstdlib>

 #include <sstream>

 using namespace std;

 typedef long long LL;

 const int INF=0x5fffffff;

 const double EXP=1e-;

 const int MS=;

 int des,n,maxv;

 double edges[MS][MS];

 int cnt[MS];

 bool flag[MS];

 struct point

 {

       int x,y;

 }points[MS];

 double distence(point &a,point &b)

 {

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

 }

 int main()

 {

       int T;

       scanf("%d",&T);

       while(T--)

       {

             scanf("%d%d%d",&des,&n,&maxv);

             int x,y;

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

             {

                   scanf("%d%d",&x,&y);

                   points[i].x=x;

                   points[i].y=y;

             }

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

                   cnt[i]=INF;

             memset(flag,false,sizeof(flag));

             queue<int > que;

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

             {

                   if(points[i].y<=maxv)

                   {

                         cnt[i]=;

                         que.push(i);

                   }

                   if(des-points[i].y<=maxv)

                         flag[i]=true;

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

                   {

                         edges[i][j]=edges[j][i]=distence(points[i],points[j]);

                   }

             }

             while(!que.empty())

             {

                   int u=que.front();

                   que.pop();

                   for(int v=;v<=n;v++)

                   {

                         if((u!=v)&&edges[u][v]<=(double)(maxv+EXP))

                               {

                                           if(cnt[u]+<cnt[v])

                                           {

                                                 cnt[v]=cnt[u]+;

                                                 que.push(v);

                                           }

                               }

                   }

             }

             if(des<=maxv)

             {

                   printf("YES\n1\n");

                   continue;

             }

             if(n==)

             {

                   if(des<=maxv)

                         printf("YES\n1\n");

                   else

                         printf("NO\n%d\n",des);

                   continue;

             }

             int ans=INF;

             int t=;

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

             {

                   if(flag[i])

                   {

                        if(cnt[i]<INF)

                         {

                               if(ans>cnt[i]+)

                                     ans=cnt[i]+;

                         }

                   }

                  if(cnt[i]<INF)

                   {

                         if(points[i].y>t)

                               t=points[i].y;

                   }

             }

             if(ans<INF)

             {

                   printf("YES\n");

                   printf("%d\n",ans);

             }

             else

             {

                   printf("NO\n");

                   printf("%d\n",des-t);

             }

       }

       return ;

 }