poj 1039

哎~~~~~~~~~~~~

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
const int maxn=25*2;
const double eps=1e-8;
struct Point
{
	double x,y;
};
int n;
double maxv;
Point up[maxn],bottom[maxn];
struct Line{
    double a, b, c;
};
double cross(Point a,Point b,Point c,Point d)
{
	return (b.x-a.x)*(d.y-c.y)-(b.y-a.y)*(d.x-c.x);
}
Line getLine(Point p1, Point p2){
    Line tmp;
    tmp.a = p1.y - p2.y;
    tmp.b = p2.x - p1.x;
    tmp.c = p1.x*p2.y - p2.x*p1.y;
    return tmp;
}
int judge(Point a,Point b,int lim)
{
	int i,j;
	int way;
	for(i=0;i<n-1;i++)
	{
		if(cross(b,a,b,up[i])>eps||cross(b,a,b,up[i+1])>eps)
		{
			way=1;
			break;
		}
		if(cross(b,a,b,bottom[i])<-eps||cross(b,a,b,bottom[i+1])<-eps)
		{
			way=2;
			break;
		}
	}
	if(i==n-1) return 1;
	if(i<lim) return 0;
	Line l1,l2;
	 l1 = getLine(a, b);
    if(way== 1) l2 = getLine(up[i], up[i+1]);
    else l2 = getLine(bottom[i], bottom[i+1]);
    maxv = max(maxv, (l1.b*l2.c-l2.b*l1.c)/(l1.a*l2.b-l2.a*l1.b));
    return 0;
}
int main()
{
	while(scanf("%d",&n)&&n)
	{
		int i,j;
		double x,y;
		for(i=0;i<n;i++)
		{
			scanf("%lf%lf",&x,&y);
			up[i].x=x;up[i].y=y;
			bottom[i].x=x;bottom[i].y=y-1;
		}
		int k;
		maxv=-1000000;
		int flag=0;
		if(n<3)  flag=1;
		for(i=0;i<n;i++)
		{
			for(j=i+1;j<n;j++)
			{
				if(judge(up[i],bottom[j],j))
				{
					flag=1;
					break;
				}	
				if(judge(bottom[i],up[j],j))
				{
					flag=1;
					break;
				}
			}
		}
		if(flag) printf("Through all the pipe.\n");
		else printf("%.2lf\n",maxv);
	}
	return 0;
}