题解：CF2002C Black Circles

3Luby3 · 2024-10-16 22:21:13 · 题解

本蒟蒻的第一篇题解，感谢支持。

题目大意

起初在 (x_i,y_i) 的 n 个圆半径都为 0，然后每秒半径增长 1 个单位。我们要从 (x_s,y_s) 移动到 (x_t,y_t)，在此之间不能碰到任何一个圆的边缘，判断能否到达目标。

解题思路

本题算法：贪心。

本题我们可以把圆心存在一个结构体里，大小开 {10}^{5}，不会爆。

我们知道两点之间直线最短，所以这道题我们从 (x_s,y_s) 到 (x_t,y_t) 时要走直线才是最短、最快的。

那要如何求两个点之间的距离呢？

公式如下：

\sqrt{{(x_2-x_1)}^{2}+({y_2-y_1})^{2}}

举个例子：

（图可能不太严谨，见谅）

这里的 (x_2,y_2) 为 (5,5)，(x_1,y_1) 为 (1,1)，代入公式，他们的距离就为 \sqrt{{(5-1)}^{2}+({5-1})^{2}}，算出来就是 \sqrt{32}。

公式说完再回到思路。我们利用这个公式就可以判断走的是不是最短的路线，如果是就输出 Yes，否则输出 No。

温馨提示

本题是多组样例，所以如果用了标记就一定要归为 0。
由于我的公式总结是写的 y_1 可能会误导大家开一个叫 y1 的变量，这是不行的，应为 y1 是一个 C++ 函数，交上去会 WA。
（优化提示）这道题目的公式可以不用开根，因为本题不是输出确切的距离，只是利用距离帮助去求最短的路线，所以可以不用开根号。

代码

AC 记录：link at CF。

#include<iostream>
#define int long long
using namespace std;
int T,n,x1,y,x2,y2;//一定记得不能用y0或y1做变量名
bool flag=false;//记得定义
struct node{
    int x,y;
}a[1000001];
int juli(int x1,int y,int x2,int y2){//计算两点之间的距离
    return (x2-x1)*(x2-x1)+(y2-y)*(y2-y);//可以不用开根号，具体见「温馨提示」
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T;//多组数据
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;//输入圆心坐标
        cin>>x1>>y>>x2>>y2;//输入起点坐标和终点坐标
        flag=false;//多组样例记得重新定义为false
        for(int i=1;i<=n;i++){
            if(juli(a[i].x,a[i].y,x2,y2)<=juli(x1,y,x2,y2)) flag=1;//判断+标记
        }
        if(flag==0) cout<<"Yes"<<endl;//如果是最短的输出Yes
        else cout<<"No"<<endl;//否则输出No
    }
    return 0;
}