D – Circumferences
本文最后更新于 733 天前,其中的信息可能已经有所发展或是发生改变。

D - Circumferences

原题链接

分析

  • 考虑BFS搜索,将相交的园加入搜索队列
  • 每次搜索判断终点是否位于圆上
  • 核心在于判断两圆是否相交,及点是否位于圆上,设圆心距为d
  • 相交:d*d <= (r1+r2)*(r1+r2) && d*d >= (r1-r2)*(r1-r2)
  • (x,y)在圆(x1,y1)上:(x1-x)*(x1-x)+(y1-y)*(y1-y) == r1*r1

注意

  • 注意数据范围需要开long long
  • 不能使用sqrtpow,会产生精度问题

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL N=1e6+3;

LL n,sx,sy,tx,ty;

struct point{   //存储圆的信息
    LL x,y,r;
}mp[N];

queue<point> st;  //用于搜索的队列

bool vis[N];  //记录该圆是否被搜到过

bool check(LL x_1,LL y_1,LL x_2,LL y_2,LL r_1,LL r_2){  //判断两圆是否相交
    return (x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2)>=(r_1-r_2)*(r_1-r_2)&&(x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2)<=(r_1+r_2)*(r_1+r_2);
}

bool in(LL x,LL y,LL r,LL a,LL b){  //判断点是否在圆上
    return (x-a)*(x-a)+(y-b)*(y-b)==r*r;
}

bool bfs(){

    while(!st.empty()){

        auto p=st.front();
        st.pop();

        if(in(p.x,p.y,p.r,tx,ty)) return 1;  //若终点在圆上直接返回

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

            if(!vis[i]){  //若没有搜到过该圆

                if(check(p.x,p.y,mp[i].x,mp[i].y,p.r,mp[i].r)){  //判断两圆是否相交
                    vis[i]=1;  //若相交,则标记该圆
                    st.push(mp[i]);  //将其加入搜索队列
                }

            }

        }

    }

    return 0;  //找不到说明走不到终点

}

int main(){

    scanf("%lld",&n);

    scanf("%lld %lld %lld %lld",&sx,&sy,&tx,&ty);

    for(int i=0;i<n;i++){
        LL a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        mp[i]={a,b,c};

        if(in(a,b,c,sx,sy)){  //若起始点在该圆上
            st.push(mp[i]);  //则将该圆作为搜索起始点加入搜索队列
            vis[i]=1;  //标记该圆已经搜到过
        }

    }

    if(bfs()) printf("Yes\n");
    else printf("No\n");

    return 0;

}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇