ZOJ Monthly, October 2010解题报告 » ZOJ3414

ZOJ3414
ZOJ3414.cpp


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

using namespace std;

const int MAXN = 1024;
double x[MAXN], y[MAXN], dx[MAXN], dy[MAXN], z[MAXN];

int main() {
	int ri = 0, n, m;
	double xx, yy, zz, zzz;

	while (scanf("%d%d", &n, &m) != EOF) {
		zzz = 0;
		x[0] = y[0] = 0;
		for (int i = 1; i <= n; ++i) {
			scanf("%lf%lf", &x[i], &y[i]);
			dx[i] = x[i] - x[i - 1];
			dy[i] = y[i] - y[i - 1];
			z[i] = hypot(dx[i], dy[i]);
			if (fabs(z[i] > 1e-8)) {
				dx[i] /= z[i];
				dy[i] /= z[i];
			}
			zzz += z[i];
		}
		zzz /= (m + 1);

		printf("Route %d\n", ++ri);
		xx = yy = 0;
		for (int i = 0, j = 1; i < m; ++i) {
			zz = zzz;
			while (z[j] <= zz) {
				xx = x[j];
				yy = y[j];
				zz -= z[j];
				++j;
			}
			xx += dx[j] * zz;
			yy += dy[j] * zz;
			z[j] -= zz;
			printf("CP%d: (%.3lf, %.3lf)\n", i + 1, xx, yy);
		}
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//899 	2010-07-21 21:14:17 	Accepted 	1094 	C++ 	300 	220 	anotherpeg 	Source

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//322 	2010-10-05 22:28:48 	Accepted 	I 	C++ 	200 	220 	watashi@Zodiac 	Source
Leave a Reply