题目地址：http://www.bailian.openjudge.cn/practice/1039
依次枚举上面和下面的任意两点所组成的直线，然后依次判断是否与每个拐点的竖线相交
判断是否相交的方法是算出该点处的y值并比较
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const double EPS=1e-6;
#define Vector Point
int n; double mx;bool IsZero(double x){ return -EPS<x&&x<EPS;
}
struct Point{double x,y;Point(double x,double y):x(x),y(y) {}Vector operator - (const Point& p){return Vector(x-p.x,y-p.y);} Point operator + (const Vector& v){return Point(v.x+x,v.y+y);}};
vector<Point> points;Vector operator * (double f,Vector v){return Vector(f*v.x,f*v.y);
}struct Segment{Point x,y;double getY(double x1){return (x1-x.x)/(y.x-x.x)*(y.y-x.y) + x.y;}Segment(Point x,Point y):x(x),y(y) {}
};
double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;
}
Point getPoint(Segment a,Segment b){Point p1=a.x,p2=a.y,p3=b.x,p4=b.y;double x=cross(p3-p1,p2-p1);double y=cross(p2-p1,p4-p1);if(IsZero(x+y)) return Point(0,0); //平行return p3+x/(x+y)*(p4-p3);
}bool solved(Point x,Point y){for(int k=0;k<n;k++){Point p1=points[k],p2=p1; p2.y--;double yk=Segment(x,y).getY(p1.x); //求出在该x点的y值 if(yk<p2.y-EPS||yk>p1.y+EPS){if(!k) return false; //若第一个拐点都过不了，直接返回 Point p3=points[k-1],p4=p3; p4.y--;mx=max(mx,getPoint(Segment(x,y),Segment(p1,p3)).x);mx=max(mx,getPoint(Segment(x,y),Segment(p2,p4)).x);return false;}mx=max(mx,p1.x);}return true;
}
int main()
{while(scanf("%d",&n)&&n){double x,y;points.clear();for(int i=0;i<n;i++){scanf("%lf%lf",&x,&y);points.push_back(Point(x,y));}int ok=1; mx=points[0].x;if(n>2)for(int i=0;i<n;i++) //枚举上面的点和下面的点 {for(int j=0;j<n;j++){if(j==i) continue; Point x=points[i],y=points[j]; y.y--;ok=0;if(solved(x,y)) ok=1;if(ok) break;}if(ok) break;}if(ok) cout<<"Through all the pipe."<<endl;else printf("%.2lf\n",mx);}return 0;
}