posted on 2021-05-03 20:50:49 | under 题解 | source
首先输入,记录一下哪个齿轮的位置在 \((0,0)\),哪个在 \((x_t,y_t)\)。
接着,为了避免多次判断两个齿轮相切而超时,我们可以预处理一个 \(link_{i,j}\),表示第 \(i\) 个齿轮是否和第 \(j\) 个齿轮相切。
这部分直接 \(O(n^2)\) 暴力即可,注意 \(link_{i,i}\) 要 \(=0\),不然 bfs 时会重复搜自己。
怎么判断两个齿轮是否相切?我们小学二年级都学过一种距离,叫「欧几里得距离」。设两个点分别在 \((x_1,y_1)\) 和 \((x_2,y_2)\),那它们的距离就是:
\[dis=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \]怎么把它运用到这道题上呢?很简单,如果两个齿轮的圆心的距离等于这两个齿轮的半径之和,就说这两个齿轮相切。
实际运用时,为了防止被卡精度,一般对等式两边开平方,也就是:
\[(x_1-x_2)^2+(y_1-y_2)^2=(r_1+r_2)^2 \]处理完 \(link_{i,j}\),就可以直接暴力 bfs 了。
bfs 的结点记录三个东西:当前是哪一个齿轮,当前齿轮的速度,当前经过齿轮的总速度。
题目要求「绝对值之和」,那就忽视计算速度这个负号。
每次扩展结点时,要选没扩展过而且与它相切的齿轮。
这样的 bfs,每个结点只会搜一次,每个结点要遍历一次 \(1\) 到 \(n\),时间复杂度为 \(O(n^2)\)。
最后输出答案要注意,直接向下取整,而不是四舍五入。
代码实现:
#include <queue>
#include <cstdio>
using namespace std;
int f(int a){return a*a;}//开平方函数,用 define 会计算很多次,不推荐
struct Roller{
int x,y,r;
Roller(int a=0,int b=0,int c=0):x(a),y(b),r(c){}
friend bool check(Roller a,Roller b){
return f(a.x-b.x)+f(a.y-b.y)<=f(a.r+b.r);//判断相切
}
friend bool operator==(Roller a,Roller b){
return a.x==b.x&&a.y==b.y;//判断相等
}
} a[1060];
int n,si,ei,ex,ey;
bool vis[1060],link[1060][1060];//vis 记录这个齿轮有没有被扩展过
struct Node{
int i;
double v,tot;//float 已死
Node(int a,double c,double d):i(a),v(c),tot(d){}
};
queue<Node> q;
int bfs(){
q.push(Node(si,10000.0,10000.0));
vis[si]=1;//搜索记得标记起点
while(!q.empty()){
Node now=q.front();q.pop();
if(now.i==ei) return (int)now.tot;//向下取整
for(int i=1;i<=n;i++){
if(!vis[i]&&link[now.i][i]){
vis[i]=1;
double v=now.v*(1.0*a[now.i].r/a[i].r);//计算扩展的齿轮的速度,注意 *1.0
q.push(Node(i,v,now.tot+v));
}
}
}
return -1;
}
int main(){
scanf("%d%d%d",&n,&ex,&ey);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);
if(a[i]==Roller(0,0)) si=i;
if(a[i]==Roller(ex,ey)) ei=i;//记录头尾
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(check(a[i],a[j])) link[i][j]=link[j][i]=1;//预处理link[i][j]
}
}
printf("%d",bfs());
return 0;
}
标签:结点,齿轮,int,题解,Loathesome,相切,bfs,P2903,Roller
From: https://www.cnblogs.com/caijianhong/p/Solution-p2903.html