1252.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1252 on 2006-02-27 at 19:50:11 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 32;
const double INF = 1e10;

class Wall {
public:
	double begin, end;
	void set(double cb, double ce) { begin = cb; end = ce; }
	bool stop(double, double, double, double, double) const;
};
bool Wall::stop(double wx, double x1, double y1, double x2, double y2) const {
	double wy = (y2-y1) / (x2-x1) * (wx-x1) + y1;
	return (wy > begin && wy < end);
}

int main()
{
	int i, j, k, l, s, t, n;
	Wall wall[MAX][3];
	double p[MAX][4], x[MAX], d[MAX][4];
	
	while(scanf("%d", &n) != EOF && n >= 0) {
		n += 2; x[0] = 0; x[n-1] =10;
		for(i = 0; i < 4; i++) { p[n-1][i] = p[0][i] = 5; d[0][i] = 0; d[n-1][i] = INF; }
		for(i = 1; i < n-1; i++) {
			scanf("%lf", &x[i]);
			for(j = 0; j < 4; j++) scanf("%lf", &p[i][j]), d[i][j] = INF;
			wall[i][0].set(0, p[i][0]); wall[i][1].set(p[i][1], p[i][2]); wall[i][2].set(p[i][3], 10);
		}
		for(i = 0; i < n; i++)
			for(j = 0; j < 4; j++)
				for(k = i+1; k < n; k++)
					for(l = 0; l < 4; l++) {
						bool pass = true;
						for(s = i+1; s < k && pass; s++)
							for(t = 0; t < 3; t++)
								if(wall[s][t].stop(x[s], x[i], p[i][j], x[k], p[k][l])) { pass = false; }
						if(pass) d[k][l] = min(d[k][l], d[i][j]+sqrt((x[i]-x[k])*(x[i]-x[k])+(p[i][j]-p[k][l])*(p[i][j]-p[k][l])));
					}
		printf("%.2lf\n", d[n-1][0]);
	}
	
	return 0;
}