狗狗40题搞完纪念 » 1017

1017
1017.cpp


#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 32;
const double EPS = 1e-6;

int main() {
	int ri = 0, n, pre, cur;
	double x0, y0, dx, dy, xx, yy, b, c, d, t, mint;
	double x[MAXN], y[MAXN], r[MAXN];

	while (scanf("%d", &n) != EOF && n > 0) {
		for (int i = 0; i < n; ++i) {
			scanf("%lf%lf%lf", &x[i], &y[i], &r[i]);
		}
		scanf("%lf%lf%lf%lf", &x0, &y0, &dx, &dy);
		d = hypot(dx, dy);
		dx /= d;
		dy /= d;

		printf("Scene %d\n", ++ri);
		pre = -1;
		for (int i = 0; i <= 10; ++i) {
			cur = -1;
			for (int j = 0; j < n; ++j) {
				if (j == pre) {
					continue;
				}
				xx = x0 - x[j];
				yy = y0 - y[j];
				b = 2 * (xx * dx + yy * dy);
				c = xx * xx + yy * yy - r[j] * r[j];
				d = b * b - 4 * c;
				if (d < -EPS) {
					continue;
				}
				d = d < 0 ? 0 : sqrt(d);
				// printf("%lf %lf d=%lf t1=%lf t2=%lf\n", b, c, d, (-b - d) / 2, (-b + d) / 2);
				if (-b - d >= -EPS) {
					t = (-b - d) / 2;
				} else {
					t = (-b + d) / 2;
				}
				if (t >= -EPS && (cur == -1 || t < mint)) {
					cur = j;
					mint = t;
				}
			}

			if (cur == -1) {
				printf("inf");
				break;
			} else if (i == 10) {
				printf("...");
				break;
			} else {
				printf("%d ", cur + 1);
				pre = cur;
				x0 += dx * mint;
				y0 += dy * mint;
				xx = x0 - x[cur];
				yy = y0 - y[cur];
				// printf("mint = %lf; hypot(%lf, %lf) = %lf\n", mint, xx, yy, hypot(xx, yy));
				d = 2 * fabs(xx * dx + yy * dy) / (xx * xx + yy * yy);
				dx += xx * d;
				dy += yy * d;
				// printf("(%lf, %lf) (%lf, %lf) = %lf [%lf]\n", x0, y0, dx, dy, hypot(dx, dy), d);
			}
		}
		puts("\n");
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//324 	2010-06-27 19:35:12 	Accepted 	1017 	C++ 	10 	180 	anotherpeg 	Source
Leave a Reply