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