比赛 |
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;
- }