题201.2022寒假天梯赛训练-7-9 拯救007 (25 分)

一、题目

在这里插入图片描述

二、题解

本题要抓住几个点。
第一，开始起跳出小岛怎么处理：虽然从岸边起跳肯定可以距离鳄鱼更近更有机会跳到但是岸是个曲线，点无数个，你没法处理，因此我们不妨利用这是个圆形的岛，将起跳点直接设置在原点，然后跳的距离多一个岛屿的半径长度即可。
第二，如何判断我能不能跳到下一个鳄鱼头上：都是一个个点，我们自然是用两点间距离公式得到距离和能跳的距离比较，如果前者小于等于后者，则可以跳过去
第三，如何判断能够跳出湖：因为湖是正方形的，四条直线段组成了四条边，你从鳄鱼头上试图往岸上跳，你肯定想看我离得最近的时候能不能跳过去啊，而最近肯定是跳垂直于岸边吧，所以直接想着看看往-x方向，+x方向，-y方向，+y方向试跳就好，看是否有一条能够跳到岸上（超过了x or y的边界）。
代码如下:

#include <bits/stdc++.h>

using namespace std;

int N,D;
int visited[101];//标记那个鳄鱼是否被跳过了，即是否点被访问过了
int flag=0;//用于标记007是否有救

struct Point
{
    int x;
    int y;
}P[101];//开个结构体数组存点坐标

double getD(Point p1,Point p2)//计算两点间距离
{
    return sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2));
}

void dfs(int v0)//改造dfs算法，传参传下标就好了，有了下标，点不愁拿不到
{
    Point p0=P[v0];
    visited[v0]=1;//标记访问
    if(p0.x-D<=-50||p0.x+D>=50||p0.y-D<=-50||p0.y+D>=50)//判断是否能跳出池子
    {
        flag=1;
        return;
    }
    if(p0.x==0&&p0.y==0)//007在原点时
    {
        for(int i=1;i<=N;i++)
        {
            if(visited[i]!=1&&getD(P[i],p0)<=D+7.5)//因为中间是个圆形的小岛，所以从小岛岸边起跳相当于从原点起跳，但是跳的距离可以多7.5m(转化成定点起跳)
            {
                dfs(i);
            }
        }
    }
    else
    {
        for(int i=1;i<=N;i++)
        {
            if(visited[i]!=1&&getD(P[i],p0)<=D)//两点间距离小于等于能跳的距离则继续dfs那个点
            {
                dfs(i);
            }
        }
    }
}

int main()
{
    cin>>N>>D;
    P[0].x=0;P[0].y=0;
    for(int i=1;i<=N;i++)
    {
        scanf("%d%d",&P[i].x,&P[i].y);
    }
    dfs(0);
    if(flag)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
}