nyoj - 1276机器设备

xiaoxiao2021-02-28  11

机器设备

时间限制: 1000 ms  |  内存限制: 65535 KB 难度: 2 描述

Alpha 公司设计出一种节能的机器设备。它的内部结构是由 N 个齿轮组成。整个机器设备有 一个驱动齿轮,当启动它时,它立即按 10,000 圈/小时转速顺时针转动,然后它又带动与它相切 的齿轮反方向,即逆时针转动。齿轮之间互相作用,每个齿轮都可能驱动着多个齿轮,最终带动 一个工作齿轮完成相应的任务。 在这套设备中,记录了每个齿轮的圆心坐标和齿轮半径。已知驱动齿轮位于(0,0),最终的 工作齿轮位于(Xt, Yt)。 Alpha 公司想知道传动序列中所有齿轮的转速。所谓传动序列,即能量由驱动齿轮传送,最 后到达工作齿轮的过程中用到的所有齿轮。能量传送过程是,在一个半径为 R,转速为 S 圈/每小 时的齿轮的带动下,与它相切的半径为 R’的齿轮的转速为-S*R/R’ 转/小时。负号的意思是, 表 示按反方向转动。

 

已知,机器设备中除了驱动齿轮以外,所有齿轮都可能被另外某个齿轮带动,并且不会出现 2 个不同的齿轮带动同一个齿轮的情况。 你的任务是计算整个传动序列中所有齿轮的能量之和。即所有齿轮转速的绝对值之和。 

输入 第一行: T 表示以下有 T 组测试数据(1≤T ≤8) 对每组测试数据: 第 1 行: N Xt Yt (2≤N ≤1100) 接下来有 N 行, Xi Yi Ri 表示 N 个齿轮的坐标和半径 i=1,2,….,N ( -5000 ≤Xi ,Yi ≤ 5000 3 ≤ Ri ≤ 1000 ) 坐标以及半径是整数 输出 每组测试数据,输出占一行,即所有齿轮转速的绝对值之和 在double范围内,输出整数部分 样例输入 1 4 32 54 0 30 20 0 0 10 32 54 20 -40 30 20 样例输出 20000 来源 河南省第九届省赛 上传者

onlinejudge

代码如下:

#include<iostream>   #include<cstdio>   #include<cmath>   #include<cstring>   using namespace std;   const int N=1105;   int vis[N],spos,epos,n;   double sp[N];   struct A{       int x,y,r;   }cor[N];      int judge(int a,int b){//判断编号为a、b的圆是否相切       int t1=abs(cor[a].x-cor[b].x);       int t2=abs(cor[a].y-cor[b].y);       int t3=cor[a].r+cor[b].r;       if(t1*t1+t2*t2==t3*t3)return 1;       else return 0;   }      void dfs(int pos,double ans){       if(pos==epos){           printf("%d\n",(int)ans);           return ;     }       for(int i=1;i<=n;i++){           if(vis[i]||i==pos)continue;           if(judge(i,pos)){//如果第i个点和第pos个点相切,就加上第i个点的转速               sp[i]=sp[pos]*cor[pos].r/cor[i].r;               vis[i]=1;               ans+=sp[i];               dfs(i,ans);               ans-=sp[i];               vis[i]=0;           }       }   }      int main(){       int t,ex,ey;       scanf("%d",&t);       while(t--){           memset(vis,0,sizeof(vis));           scanf("%d%d%d",&n,&ex,&ey);           for(int i=1;i<=n;i++){               scanf("%d%d%d",&cor[i].x,&cor[i].y,&cor[i].r);               if(cor[i].x==0&&cor[i].y==0){spos=i;sp[i]=10000;}               if(cor[i].x==ex&&cor[i].y==ey)epos=i;           }           vis[spos]=1;           dfs(spos,sp[spos]);       }   }  
转载请注明原文地址: https://www.6miu.com/read-2800171.html

最新回复(0)