1046.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1046 on 2006-02-12 at 01:23:04 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 32;
const double INF = -1e10;
const double eps = 1e-4;

class Point {
public:
	double x, y;
};

double bx;

class Line {
public:
	Point v1, v2;
	bool legal(Point&, Point&) const;
	bool stop(Point&, Point&) const;
};
bool Line::legal(Point& d, Point& u) const {
	double y = (v1.y*(v2.x-d.x) - v2.y*(v1.x-d.x)) / (v2.x-v1.x);
	return (d.y-y < eps && y-u.y < eps);
}
bool Line::stop(Point& s1, Point& s2) const {
	double k1 = (v2.y-v1.y)/(v2.x-v1.x), k2 = (s2.y-s1.y)/(s2.x-s1.x);
	double b1 = v1.y-k1*v1.x, b2 = s1.y-k2*s1.x;
	if(fabs(k1-k2) < eps) return false;
	double x = (b1 - b2) / (k2 - k1);
	if(max(s1.x, s2.x)-x < eps || x-min(s1.x, s2.x) < eps) return false;
	bx = max(x, bx); return true;
}


int main()
{
	Point up[MAX], down[MAX];
	int i, j, k, n;
	Line light;

	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) {
			scanf("%lf %lf", &up[i].x, &up[i].y);
			down[i].x = up[i].x; down[i].y = up[i].y-1;
		}
		bx = INF;
		bool through = false;
		for(i = 0; i < n && !through; i++)
			for(j = 0; j < n && !through; j++) {
				if(i == j) continue;
				int lmt = min(i, j);
				light.v1 = up[i]; light.v2 = down[j];
				for(k = 0; k < lmt; k++)
					if(!light.legal(down[k], up[k])) break;
				if(k != lmt) continue;
				for(k = lmt+1; k < n; k++) {
					if(light.stop(up[k-1], up[k]) || light.stop(down[k-1], down[k])) break;
					if(!light.legal(down[k], up[k])) break;
				}
				if(k == n) through = true;
			}
		if(through) printf("Through all the pipe.\n");
		else printf("%.2lf\n", bx);
	}
	
	return 0;
}