1039.c

北大ACM网站 1039题 http://acm.pku.edu.cn/JudgeOnline/problem?id=1039

#include <stdio.h>
#include <float.h>

typedef double db;
int n;
db x[32];
db y[32];

db xintersect(db x0, db y0, db x1, db y1, db xp, db yp, db k)
{
	return ((k * xp + y0 - yp) * (x1 - x0) + x0 * (y0 - y1)) / (k * (x1 - x0) + (y0 - y1));
}

db check(db x0, db y0)
{
	int i;
	db k1, k2, l1, l2;
	
	k1 = -DBL_MAX;
	k2 = +DBL_MAX;

	for(i = 0; i < n; i++)
	{
		if(x[i] == x0)
			continue;

		l1 = ((y[i] - 1.) - y0) / (x[i] - x0);
		l2 = (y[i] - y0) / (x[i] - x0);
		
		if(l1 > l2)
		{			
			if((l1 < k1) || (l2 > k2)) return x[0];

			if(l1 < k2) k2 = l1;
			if(l2 > k1) k1 = l2;
		}
		else
		{
			if(l1 > k2) return xintersect(x[i-1], y[i-1] - 1., x[i], y[i] - 1., x0, y0, k2);
			if(l2 < k1) return xintersect(x[i-1], y[i-1], x[i], y[i], x0, y0, k1);
			if(l2 < k2) k2 = l2;
			if(l1 > k1) k1 = l1;
		}
	}

	return x[n-1];
}

int main(void)
{
	int i;
	db c, r;

	while (scanf("%d", &n), n)
	{
		for(i = 0; i < n; i++)
			scanf("%lf%lf", x+i, y+i);

		r = x[0];
		for(i = 0; i < n; i++)
		{
			c = check(x[i], y[i]);
			if(c > r) r = c;

			c = check(x[i], y[i] - 1.);
			if(c > r) r = c;

			if(r == x[n-1]) break;
		}

		if(r == x[n-1]) printf("Through all the pipe.\n");
		else printf("%.2f\n", r);
	}
	return 0;
}