Advertisement
Guest User

Untitled

a guest
Feb 18th, 2020
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.32 KB | None | 0 0
  1. #ifdef DEBUG
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4. //#pragma GCC optimize("O3")
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long double ld;
  8. typedef long long ll;
  9. #define y0 gsjglsg
  10. #define y1 gsjldgjsg
  11. int n;
  12. const int maxN = 55;
  13. ld x[maxN], y[maxN], z[maxN], r[maxN];
  14. ld x0, y0, z0;
  15. ld x1, y1, z1;
  16. int main() {
  17. ios_base::sync_with_stdio(false);
  18. cin.tie(nullptr);
  19. //freopen("input.txt", "r", stdin);
  20. cin >> n;
  21. for (int i = 1; i <= n; i++) {
  22. cin >> x[i] >> y[i] >> z[i] >> r[i];
  23. }
  24. cin >> x0 >> y0 >> z0;
  25. cin >> x1 >> y1 >> z1;
  26. const ld eps = 1e-6;
  27. for (int iter = 0; iter <= 10; iter++) {
  28. pair < ld, int > best = make_pair(1e18, -1);
  29. for (int i = 1; i <= n; i++) {
  30. ld dirX = x1 - x0;
  31. ld dirY = y1 - y0;
  32. ld dirZ = z1 - z0;
  33. ld A = dirX * dirX + dirY * dirY + dirZ * dirZ;
  34. ld B = 2 * dirX * (x0 - x[i]) + 2 * dirY * (y0 - y[i]) + 2 * dirZ * (z0 - z[i]);
  35. ld C = (x0 - x[i]) * (x0 - x[i]) + (y0 - y[i]) * (y0 - y[i]) + (z0 - z[i]) * (z0 - z[i]) - r[i] * r[i];
  36. ld D = B * B - 4 * A * C;
  37. // assert(abs(D) > eps);
  38. if (D < -eps) continue;
  39. ld t1 = (-B - sqrt(D)) / (2 * A);
  40. ld t2 = (-B + sqrt(D)) / (2 * A);
  41. if (t1 > eps) best = min(best, {t1, i});
  42. if (t2 > eps) best = min(best, {t2, i});
  43. }
  44. if (best.second == -1) {
  45. break;
  46. }
  47. int where = best.second;
  48. ld t = best.first;
  49. if (iter == 10) {
  50. cout << "etc.";
  51. return 0;
  52. }
  53. cout << where << " ";
  54. ld xr = x0 + t * (x1 - x0);
  55. ld yr = y0 + t * (y1 - y0);
  56. ld zr = z0 + t * (z1 - z0);
  57. ld vecX = xr - x[where];
  58. ld vecY = yr - y[where];
  59. ld vecZ = zr - z[where];
  60. ld A = vecX * vecX + vecY * vecY + vecZ * vecZ;
  61. ld B = vecX * (x[where] - x0) + vecY * (y[where] - y0) + vecZ * (z[where] - z0);
  62. t = -B / A;
  63. ld midX = x[where] + t * vecX;
  64. ld midY = y[where] + t * vecY;
  65. ld midZ = z[where] + t * vecZ;
  66. x1 = 2 * midX - x0;
  67. y1 = 2 * midY - y0;
  68. z1 = 2 * midZ - z0;
  69. x0 = xr;
  70. y0 = yr;
  71. z0 = zr;
  72. }
  73. return 0;
  74. }
  75. close
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement