SGU 110 Dungeon

//By momo
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100
#define INF 999999999
#define EPS 1e-7
using namespace std;

int n, prv = -1;
double x[N], y[N], z[N], r[N];
double sx, sy, sz, vx, vy, vz;

double sq(double a){ return a*a; }
double findx2(double a, double b, double c){
    if(sq(b) - 4*a*c + EPS >= 0){
        double x1 = ( sqrt(sq(b) - 4*a*c) - b) / (2*a);
        double x2 = (-sqrt(sq(b) - 4*a*c) - b) / (2*a);
        if(x2 >= 0) return x2;
        return x1;
    }
    return -1;
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%lf%lf%lf%lf", &x[i], &y[i], &z[i], &r[i]);
    scanf("%lf%lf%lf%lf%lf%lf", &sx, &sy, &sz, &vx, &vy, &vz); vx -= sx, vy -= sy, vz -= sz;
    for(int t = 0; t < 11; t++){
        double P = INF;
        int idx = 0;
        for(int i = 0; i < n; i++){
            if(i == prv) continue;
            double a = vx*vx + vy*vy + vz*vz;
            double b = 2*(vx*(sx-x[i]) + vy*(sy-y[i]) + vz*(sz-z[i]));
            double c = sq(sx-x[i]) + sq(sy-y[i]) + sq(sz-z[i]) - sq(r[i]);
            double ans = findx2(a, b, c);
            if(ans+EPS >= 0 && P+EPS > ans) P = ans, idx = i;
        }
        if(P+EPS > INF && P < INF+EPS) break;
        if(t == 10) printf("etc.");
        else printf("%d ", idx+1);
        prv = idx;
        double nx = x[idx] - (sx + P*vx);
        double ny = y[idx] - (sy + P*vy);
        double nz = z[idx] - (sz + P*vz);
        double ln = sqrt(sq(nx) + sq(ny) + sq(nz));
        nx /= ln, ny /= ln, nz /= ln;
        double dt = vx*nx + vy*ny + vz*nz;
        sx += P*vx, sy += P*vy, sz += P*vz;
        vx -= 2*dt*nx, vy -= 2*dt*ny, vz -= 2*dt*nz;
    }
    puts("");
}