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

时间:2023-04-02 20:13:50

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

2
4 3 1
0 1
0 2
0 3
6 3 2
0 1
1 2
2 3

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 ;
}