比赛 |
20111102 |
评测结果 |
RRRRRRRRRR |
题目名称 |
麻烦的干草打包机 |
最终得分 |
0 |
用户昵称 |
王者自由 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-11-02 20:33:09 |
显示代码纯文本
#include <cstdio>
#define MAX 2011
struct gear {
int x, y, r;
} g[MAX];
struct queue {
int d, pre;
} q[MAX];
int i, j, head, tail = 1, n, xt, yt, num, drv;
double s, d[MAX];
bool b[MAX];
inline int sqr(int x) {
return x * x;
}
int main() {
freopen("egroup.in", "r", stdin);
freopen("egroup.out", "w", stdout);
scanf("%d %d %d", &n, &xt, &yt);
for(i=1; i<=n; i++) {
scanf("%d %d %d", &g[i].x, &g[i].y, &g[i].r);
if(g[i].x == xt && g[i].y == yt)
num = i;
if(g[i].x == 0 && g[i].y == 0)
drv = i;
}
q[tail].d = drv, b[drv] = true, d[drv] = 10000;
do {
head++;
for(i=1; i<=n; i++) {
j = q[head].d;
if(!b[i] && sqr(g[j].r + g[i].r) ==
sqr(g[j].x - g[i].x) + sqr(g[j].y - g[i].y)) {
b[i] = true;
tail++;
q[tail].d = i, q[tail].pre = head;
d[i] = d[j] * (double)g[j].r / g[i].r;
if(i == num) break;
}
}
} while(!(head >= tail || b[num]));
if(!b[num])
printf("0\n");
else {
for(i = tail; i != 0; i = q[i].pre)
s += d[q[i].d];
printf("%.0lf\n", s);;
}
return 0;
}