比赛 20111102 评测结果 RRRRRRRRRR
题目名称 麻烦的干草打包机 最终得分 0
用户昵称 王者自由 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-11-02 20:33:09
显示代码纯文本
  1. #include <cstdio>
  2. #define MAX 2011
  3. struct gear {
  4. int x, y, r;
  5. } g[MAX];
  6. struct queue {
  7. int d, pre;
  8. } q[MAX];
  9. int i, j, head, tail = 1, n, xt, yt, num, drv;
  10. double s, d[MAX];
  11. bool b[MAX];
  12. inline int sqr(int x) {
  13. return x * x;
  14. }
  15. int main() {
  16. freopen("egroup.in", "r", stdin);
  17. freopen("egroup.out", "w", stdout);
  18. scanf("%d %d %d", &n, &xt, &yt);
  19. for(i=1; i<=n; i++) {
  20. scanf("%d %d %d", &g[i].x, &g[i].y, &g[i].r);
  21. if(g[i].x == xt && g[i].y == yt)
  22. num = i;
  23. if(g[i].x == 0 && g[i].y == 0)
  24. drv = i;
  25. }
  26. q[tail].d = drv, b[drv] = true, d[drv] = 10000;
  27. do {
  28. head++;
  29. for(i=1; i<=n; i++) {
  30. j = q[head].d;
  31. if(!b[i] && sqr(g[j].r + g[i].r) ==
  32. sqr(g[j].x - g[i].x) + sqr(g[j].y - g[i].y)) {
  33. b[i] = true;
  34. tail++;
  35. q[tail].d = i, q[tail].pre = head;
  36. d[i] = d[j] * (double)g[j].r / g[i].r;
  37. if(i == num) break;
  38. }
  39. }
  40. } while(!(head >= tail || b[num]));
  41. if(!b[num])
  42. printf("0\n");
  43. else {
  44. for(i = tail; i != 0; i = q[i].pre)
  45. s += d[q[i].d];
  46. printf("%.0lf\n", s);;
  47. }
  48. return 0;
  49. }