poj1039，直线交点

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

struct Point{
	double x,y;
	Point(double x=0,double y=0):x(x),y(y){
	};
	Point operator-(Point b){return Point(x-b.x,y-b.y);
	}
	double operator^(Point b){return x*b.y-y*b.x;
	}
	Point operator+(Point b){return Point(x+b.x,y+b.y);
	}
};

struct Line{
	Point s,e;
	Line(Point s,Point e):s(s),e(e){
	};
	Line(){
	};
};

struct Seg{
	Point s,e;
	Seg(Point s,Point e):s(s),e(e){
	};
	Seg(){
	};
};

int sgn(double x){
	if(fabs(x)<1e-8) return 0;
	if(x>0) return 1;
	return -1;
}

int lineInterSeg(Line l1,Seg l2){//直线与线段相交 
    if(sgn((l1.s-l1.e)^(l2.s-l2.e))==0){//两直线方向平行
            if(sgn((l1.s-l2.e)^(l1.s-l1.e))==0) return 1; //l2的e点在直线l1上，两直线重合 
            else return 0; //直线与线段平行 ,不相交 
    }else{
        if(sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0) return 2;//l2两个端点在直线l1的两侧 ,若严格相交去= 
        else return 0;//否则不相交，线段在直线的一侧 
    } 
      
}//不相交为0，重合为1，相交为2

const int N=30;
int n;
Point point[N<<1];

Point cross(Line a,Line b){//必须确定两个直线是相交的，或者线段 ，本函数不判断相交性 
	Point res=a.s;
	double t=((a.s-b.s)^(b.s-b.e))/((a.s-a.e)^(b.s-b.e));
	res.x+=(a.e.x-a.s.x)*t;
	res.y+=(a.e.y-a.s.y)*t;
	return res;
}

int main(int argc, char** argv) {
	while(scanf("%d",&n)==1&&n){
		double ans=-9999999;
		int flag=0;
		for(int i=0;i<n;i++){
			scanf("%lf%lf",&point[i].x,&point[i].y);
			point[i+n]=point[i]+Point(0,-1);
		}
		for(int i=0;i<n;i++){
			for(int j=n;j<n<<1;j++){
				if(i==j+n) continue;
				int g=0;
				for( g=0;g<n;g++){
					if(g==0){//第一组点为发光处 
						if(lineInterSeg(Line(point[i],point[j]),Seg(point[g],point[g+n]))) continue;//经发光处，跳过下面非第一组时的处理 
						else break;//没经过发光处，不可能的光线，break丢掉 
					}
					if(!lineInterSeg(Line(point[i],point[j]),Seg(point[g],point[g+n]))){//因为是顺序找，所以找到是第一组线段两个都在直线一侧的 ，即直线没穿过线段的点 
						Point cp=cross(Line(point[i],point[j]),Line(point[g],point[g-1]));//直线射到的最远处要么在上线段，要么在下线段
						ans=max(cp.x,ans);		//这里是直线求交点，上下两边都是平行，所以就算比如是这组上边有交点，但下边的延长线与直线的交点一定在上边交点的前面
						cp=cross(Line(point[i],point[j]),Line(point[g+n],point[g+n-1]));//下边求交点 
						ans=max(cp.x,ans);
						break;
					}
				}
				if(g==n) flag=1;//如果直线全部穿过，flag=1 
			}
		}
		if(flag) printf("Through all the pipe.\n");
		else printf("%.2f\n",ans);
	}
	return 0;
}

Point cross(Line a,Line b){//必须确定两个直线是相交的，或者线段 ，本函数不判断相交性 
	double	a1=a.s.y-a.e.y,	b1=a.e.x-a.s.x,	c1=a.s^a.e,
			a2=b.s.y-b.e.y,	b2=b.e.x-b.s.x,	c2=b.s^b.e,
			d=a1*b2-a2*b1;
	//d如果为0，即sgn(d)==0，则没有交点
	return Point((b1*c2-b2*c1)/d,(a2*c1-a1*c2)/d);
}