Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef DEBUG
- #define _GLIBCXX_DEBUG
- #endif
- //#pragma GCC optimize("O3")
- #include <bits/stdc++.h>
- using namespace std;
- typedef long double ld;
- typedef long long ll;
- #define y0 gsjglsg
- #define y1 gsjldgjsg
- int n;
- const int maxN = 55;
- ld x[maxN], y[maxN], z[maxN], r[maxN];
- ld x0, y0, z0;
- ld x1, y1, z1;
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- //freopen("input.txt", "r", stdin);
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> x[i] >> y[i] >> z[i] >> r[i];
- }
- cin >> x0 >> y0 >> z0;
- cin >> x1 >> y1 >> z1;
- const ld eps = 1e-6;
- for (int iter = 0; iter <= 10; iter++) {
- pair < ld, int > best = make_pair(1e18, -1);
- for (int i = 1; i <= n; i++) {
- ld dirX = x1 - x0;
- ld dirY = y1 - y0;
- ld dirZ = z1 - z0;
- ld A = dirX * dirX + dirY * dirY + dirZ * dirZ;
- ld B = 2 * dirX * (x0 - x[i]) + 2 * dirY * (y0 - y[i]) + 2 * dirZ * (z0 - z[i]);
- ld C = (x0 - x[i]) * (x0 - x[i]) + (y0 - y[i]) * (y0 - y[i]) + (z0 - z[i]) * (z0 - z[i]) - r[i] * r[i];
- ld D = B * B - 4 * A * C;
- // assert(abs(D) > eps);
- if (D < -eps) continue;
- ld t1 = (-B - sqrt(D)) / (2 * A);
- ld t2 = (-B + sqrt(D)) / (2 * A);
- if (t1 > eps) best = min(best, {t1, i});
- if (t2 > eps) best = min(best, {t2, i});
- }
- if (best.second == -1) {
- break;
- }
- int where = best.second;
- ld t = best.first;
- if (iter == 10) {
- cout << "etc.";
- return 0;
- }
- cout << where << " ";
- ld xr = x0 + t * (x1 - x0);
- ld yr = y0 + t * (y1 - y0);
- ld zr = z0 + t * (z1 - z0);
- ld vecX = xr - x[where];
- ld vecY = yr - y[where];
- ld vecZ = zr - z[where];
- ld A = vecX * vecX + vecY * vecY + vecZ * vecZ;
- ld B = vecX * (x[where] - x0) + vecY * (y[where] - y0) + vecZ * (z[where] - z0);
- t = -B / A;
- ld midX = x[where] + t * vecX;
- ld midY = y[where] + t * vecY;
- ld midZ = z[where] + t * vecZ;
- x1 = 2 * midX - x0;
- y1 = 2 * midY - y0;
- z1 = 2 * midZ - z0;
- x0 = xr;
- y0 = yr;
- z0 = zr;
- }
- return 0;
- }
- close
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement