题意：给一个曲折的管道，求从入口射入的光线到达最远的位置的X左标.
思路： 到达最远的光线一定经过上方和下方的折点，枚举即可。
1 #include<iostream>
2 #include<cmath>
3 #include<cstdio>
4 using namespace std;
5 #define MAXN 21
6 #define EPS 1e-8
7 #define INF 1<<30
8 struct point
9 {
10 double x,y;
11 point() {}
12 point(double x0,double y0): x(x0),y(y0) {}
13 };
14 int n;
15 point a[MAXN],b[MAXN];
16 point operator -(const point &A,const point &B)
17 {
18 return point(A.x-B.x,A.y-B.y);
19 }
20 double cross(point A,point B)
21 {
22 return A.x*B.y-B.x*A.y;
23 }
24 int dblcmp(double p)
25 {
26 if(fabs(p)<EPS) return 0;
27 return p>0 ? 1:-1;
28 }
29 bool is_intersect(point p1,point p2,point p3,point p4)
30 {
31 return dblcmp(cross(p3-p2,p1-p2))*dblcmp(cross(p4-p2,p1-p2))<=0;
32 }
33 double find_intersection(point p1,point p2,point p3,point p4)
34 {
35 if(!is_intersect(p1,p2,p3,p4)) return INF;
36 double s1=fabs(cross(p3-p1,p2-p1));
37 double s2=fabs(cross(p4-p1,p2-p1));
38 return (p3.x*s2+p4.x*s1)/(s1+s2);
39 }
40
41 void solve()
42 {
43 double sum=a[n].x;
44 double ans=-INF;
45 int i,j,k;
46 double x1,x2;
47 point p1,p2;
48 int Min,Max;
49 double left,right;
50 for(i=1;i<=n;i++)
51 for(j=1;j<=n;j++)
52 if(i!=j)
53 {
54 Min=min(i,j); Max=max(i,j);
55 left=a[1].x; right=a[n].x;
56 for(k=Min;k<=Max;k++)
57 {
58 if(!is_intersect(a[i],b[j],a[k],b[k])) break;
59 }
60 if(k<=Max) continue;
61 for(k=Min;k>0;k--)
62 {
63 if(!is_intersect(a[i],b[j],a[k],b[k]))
64 break;
65 }
66 if(k>0)
67 {
68 x1=find_intersection(a[i],b[j],a[k],a[k+1]);
69 x2=find_intersection(a[i],b[j],b[k],b[k+1]);
70 if(x1<INF) left=x1;
71 if(x2<INF&&x2<x1) left=x2;
72
73 }
74 for(k=Max;k<=n;k++)
75 {
76 if(!is_intersect(a[i],b[j],a[k],b[k]))
77 break;
78 }
79 if(k<=n)
80 {
81 x1=find_intersection(a[i],b[j],a[k],a[k-1]);
82 x2=find_intersection(a[i],b[j],b[k],b[k-1]);
83 if(x1<INF) right=x1;
84 if(x2<INF&&(x2>x1||x1==INF)) right=x2;
85 }
86 if(left>a[1].x) continue;
87 if(right>ans) ans=right;
88 if(dblcmp(ans-sum)==0) break;
89 }
90 if(dblcmp(ans-sum)==0)
91 {
92 printf("Through all the pipe.\n");
93 }
94 else printf("%.2lf\n",ans);
95 }
96 int main()
97 {
98 while(scanf("%d",&n)==1&&n)
99 {
100 int i;
101 for(i=1;i<=n;i++)
102 {
103 scanf("%lf%lf",&a[i].x,&a[i].y);
104 b[i].x=a[i].x; b[i].y=a[i].y-1;
105 }
106 solve();
107 }
108 return 0;
109 }