第九届河南省程序设计大赛

E 机器设备

内存限制:64MB


时间限制:1s


Special Judge: No

题目描述:

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

首先一定要看对题意，我今天下午三个小时才把这道题写出来，自己太笨啦

用广搜就可以但是最后输出的是从目标轮到驱动轮之间路径上所有的轮子，比如说样例中左上角那个轮子，虽然也会转动，但是并不会算到输出里边，

另外最后要求是输出整数部分，比如就算是18.9，也只能输出18

还有驱动轮的初速度是10000，不是1000，

我今天被这几个点坑惨了，哎，还是自己太笨能力不够，不够细心，以后注意

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{
    double x,y,r,s,sum;
}qu1[1205];
struct nide
{
    double x,y,r,s,sum;
}qu2[1205];
int main()
{
    int t,n,x1,y1,r1;
    int book[1205]={0};
    cin>>t;
    while(t--)
    {
        memset(book,0,sizeof(book));
        int head=1;
        int tail=1;
        cin>>n>>x1>>y1;
        for(int i=0;i<n;i++){
            cin>>qu1[i].x>>qu1[i].y>>qu1[i].r;
            if(qu1[i].x==0&&qu1[i].y==0){
                qu2[tail].x=qu1[i].x;
                qu2[tail].y=qu1[i].y;
                qu2[tail].r=qu1[i].r;
                qu2[tail].s=10000;
                qu2[tail].sum=10000;
                book[i]=1;
                tail++;
            }
        }
        while(head<tail){
            double a,b,c,d;
            a=qu2[head].x;
            b=qu2[head].y;
            c=qu2[head].r;
            d=qu2[head].s;
            int k1=0;
            for(int i=0;i<n;i++){
                if(book[i]==0&&sqrt((a-qu1[i].x)*(a-qu1[i].x)+(b-qu1[i].y)*(b-qu1[i].y))==(c+qu1[i].r))
                {
                    qu2[tail].x=qu1[i].x;
                    qu2[tail].y=qu1[i].y;
                    qu2[tail].r=qu1[i].r;
                    qu2[tail].s=d*(c/qu2[tail].r);
                    qu2[tail].sum=qu2[tail].s+qu2[head].sum;
                    book[i]=1;
                    if(qu2[tail].x==x1&&qu2[tail].y==y1){
                        k1=1;
                        long long int k2=(long long int)qu2[tail].sum;
                        printf("%lld\n",k2);
                        break;
                    }
                    tail++;
                }
            }
            if(k1==1)break;
            head++;
        }
    }
    return 0;
}