p110.ans1
======================
1

=================
p110.ans2
======================
1 2 1 2 1 2 1 2 1 2 etc.

=================
p110.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const double EPS = 1e-6;

struct Vec3 {
    double x, y, z;
    Vec3(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) {}
    Vec3 operator+(const Vec3& o) const {
        return Vec3(x + o.x, y + o.y, z + o.z);
    }
    Vec3 operator-(const Vec3& o) const {
        return Vec3(x - o.x, y - o.y, z - o.z);
    }
    Vec3 operator*(double k) const { return Vec3(x * k, y * k, z * k); }
    double dot(const Vec3& o) const { return x * o.x + y * o.y + z * o.z; }
    double norm() const { return sqrt(dot(*this)); }
    Vec3 normalize() const {
        double n = norm();
        return Vec3(x / n, y / n, z / n);
    }
};

struct Sphere {
    Vec3 center;
    double r;
};

int n;
vector<Sphere> spheres;
Vec3 origin, dir;

double ray_sphere_intersect(Vec3 O, Vec3 D, const Sphere& s) {
    // Find parameter t where ray P(t) = O + t*D intersects sphere:
    //
    //     |P - C|^2 = r^2
    //     |O + t*D - C|^2 = r^2
    //
    // Let V = O - C, then |V + t*D|^2 = r^2.
    //
    //     (V + t*D) . (V + t*D) = r^2
    //     V . V + 2t(V . D) + t^2(D . D) = r^2
    //
    // This gives quadratic equation:
    //   a*t^2 + b*t + c = 0
    //   where a = D . D, b = 2(V . D), c = V . V - r^2
    //
    // This function returns smallest positive t, or -1 if no valid
    // intersection.

    Vec3 V = O - s.center;
    double a = D.dot(D);
    double b = 2 * V.dot(D);
    double c = V.dot(V) - s.r * s.r;
    double disc = b * b - 4 * a * c;
    if(disc < -EPS) {
        return -1;
    }
    disc = sqrt(max(0.0, disc));
    double t1 = (-b - disc) / (2 * a);
    double t2 = (-b + disc) / (2 * a);
    if(t1 > EPS) {
        return t1;
    }
    if(t2 > EPS) {
        return t2;
    }
    return -1;
}

Vec3 reflect(Vec3 D, Vec3 N) {
    // Reflect incident direction D about normal N.
    // Decompose D into parallel and perpendicular components to N:
    //   D_parallel = (D . N)N, D_perp = D - D_parallel
    // Reflection reverses the parallel component:
    //   R = D_perp - D_parallel = D - 2*D_parallel = D - 2(D . N)N

    return D - N * (2 * D.dot(N));
}

void read() {
    cin >> n;
    spheres.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> spheres[i].center.x >> spheres[i].center.y >>
            spheres[i].center.z >> spheres[i].r;
    }
    double x1, y1, z1, x2, y2, z2;
    cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
    origin = Vec3(x1, y1, z1);
    dir = Vec3(x2 - x1, y2 - y1, z2 - z1).normalize();
}

void solve() {
    // We can solve this problem in a straight forward way - we just need to
    // implement some 3D geometry functions. In particular, we want to be able
    // to get intersections, tangents and reflection vectors, all of which have
    // closed forms. Then we can simulate the first 10 hits.

    vector<int> hits;
    int last_hit = -1;
    for(int step = 0; step < 11; step++) {
        double best_t = 1e18;
        int best_sphere = -1;
        for(int i = 0; i < n; i++) {
            if(i == last_hit) {
                continue;
            }
            double t = ray_sphere_intersect(origin, dir, spheres[i]);
            if(t > 0 && t < best_t) {
                best_t = t;
                best_sphere = i;
            }
        }
        if(best_sphere == -1) {
            break;
        }

        hits.push_back(best_sphere + 1);
        last_hit = best_sphere;

        Vec3 P = origin + dir * best_t;
        Vec3 N = (P - spheres[best_sphere].center).normalize();
        dir = reflect(dir, N).normalize();
        origin = P;
    }

    int output_count = min((int)hits.size(), 10);
    for(int i = 0; i < output_count; i++) {
        if(i > 0) {
            cout << " ";
        }
        cout << hits[i];
    }
    if(hits.size() > 10) {
        cout << " etc.";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p110.in1
======================
1 
0 0 2 1 
0 0 0 0 0 1

=================
p110.in2
======================
2 
0 0 2 1 
0 0 -2 1 
0 0 0 0 0 100

=================
statement.txt
======================
110. Dungeon

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


The mission of space explorers found on planet M the vast dungeon. One of the dungeon halls is fill with the bright spheres. The explorers find out that the light rays reflect from the surface of the spheres according the ordinary law (the incidence angle is equal to the reflectance angle, the incidence ray, the reflected ray and the perpendicular to the sphere surface lay in the one plane). The ancient legend says that if the light ray will reflect from the spheres in the proper order, than the door to the room with very precious ancient knowledge will open. You are not to guess the right sequence; your task is much simpler. You are given the positions and the radii of the spheres, the place where the laser shot was made and the direction of light propagation. And you must find out the sequence in which the light will be reflected from the spheres.


Input

The first line of input contains the single integer n (1≤n≤50) - the amount of the spheres. The next n lines contain the coordinates and the radii of the spheres xi, yi, zi, ri (the integer numbers less or equal to 10000 by absolute value). The last line contains 6 real numbers - the coordinates of two points. The first one gives the coordinates of the place of laser shot, and the second gives the direction in which it was made (the second point is the point on the ray). The starting point of the ray lies strictly outside of any sphere.


Output

Your program must output the sequence of sphere numbers (spheres are numbers from 1 as they was given in input), from which the light ray was reflected. If the ray will reflect more the 10 times, than you must output first 10, then a space and the word 'etc.' (without quotes). Notice: if the light ray goes at a tangent to the sphere you must assume that the ray was reflected by the sphere.


Sample Input 1

1 
0 0 2 1 
0 0 0 0 0 1
Sample Output 1

1
Sample Input 2

2 
0 0 2 1 
0 0 -2 1 
0 0 0 0 0 100
Sample Output 2

1 2 1 2 1 2 1 2 1 2 etc.

=================
