// Gokuri #include #include #include #include #include #include #include #include #include #include using namespace std; #define FNAME "reflect.txt" #define fin cin typedef complex dcomp; struct line { dcomp start; dcomp dir; }; struct circle { dcomp center; double r; }; #define EPSILON 1.0E-6 static inline double inprod(const dcomp& a, const dcomp& b) { return a.real() * b.real() + a.imag() * b.imag(); } static inline dcomp reflect(const dcomp& vec, const dcomp& nvec) { return vec - 2 * inprod(vec, nvec) * nvec; } bool collides(const line& l, const circle& c, double& tout, dcomp& poc) { const dcomp sd = l.start - c.center; const double lsd = inprod(l.dir, sd); double d = lsd * lsd - norm(l.dir) * (norm(sd) - c.r * c.r); //cout << "d=" << d << endl; if(d < 0.0) return false; if(fabs(d) <= EPSILON) { double t = - lsd / norm(l.dir); //cout << t << endl; if(t > EPSILON) { tout = t, poc = l.start + t * l.dir; return true; } return false; } double t1 = (-lsd + sqrt(d)) / norm(l.dir); double t2 = (-lsd - sqrt(d)) / norm(l.dir); //cout << "2p: " << t2 << " and " << t1 << endl; if(t2 > EPSILON) { tout = t2, poc = l.start + t2 * l.dir; return true; } if(t1 > EPSILON) { tout = t1, poc = l.start + t1 * l.dir; return true; } return false; } void trav(int lev, const line& l, const vector& scene) { //cout << "----- lev=" << lev << " -----" << endl; if(lev) cout << ' '; if(lev > 10) { abort(); } double tmin; dcomp pocmin; int minat = -1; for(int i = 0; i < scene.size(); i++) { double t; dcomp poc; if(collides(l, scene[i], t, poc)) { //cout << "col " << i << ", t=" << t << endl; if(minat < 0 || t < tmin) { minat = i; tmin = t; pocmin = poc; } } } if(minat < 0) { cout << "inf" << endl; return; } if(lev >= 10) { cout << "..." << endl; return; } cout << minat+1; dcomp nvec = pocmin - scene[minat].center; nvec /= abs(nvec); line nextl = {pocmin, reflect(l.dir, nvec)}; trav(lev + 1, nextl, scene); } void solve(const vector& scene, const line& l) { trav(0, l, scene); } int main(void) { ifstream fin(FNAME); if (!fin) { return 1; } // INPUT HERE int ncase = 0; int nc; while(cin >> nc, nc) { vector scene; line l; double x, y; for(int i = 0; i < nc; i++) { circle c; cin >> x >> y >> c.r; c.center = dcomp(x, y); scene.push_back(c); } cin >> x >> y; l.start = dcomp(x, y); cin >> x >> y; l.dir = dcomp(x, y); cout << "Scene " << ++ncase << endl; solve(scene, l); cout << endl; } return 0; }