poj 1039Pipe解题报告

这题的题意是一个通光的管道，假设这种材质不反射光，求从入口任意方向进入的光所能达到的最大的横坐标大小，如果有光能够完全通过管道则输出Through all the pipe.否则输出最大的横坐标值，可以证明的是，最长距离的光一定是经过某两个顶点的，假设有有一条光线不经过顶点，那么通过平移，旋转到顶点上之后所能得到的值一定比原来的要大，所以可以枚举每两个顶点的直线，从左到右依次判断是否在拐点的内部，如果不在说明和前一个拐点所购成了两个线段之间有一条是相交的，那么交点就是最大值

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define N 21
 6 #define eps 1e-5
 7 #define left -10e8
 8 using namespace std;

 9 struct point
10 {
11     double x,y;
12 };
13 point up[N],down[N];
14 int n;
15 double getx(point p1,point p2,point p3,point p4)//找到直线和线段相交的横坐标
16 {
17     double k1=(p2.y-p1.y)/(p2.x-p1.x);
18     double k2=(p4.y-p3.y)/(p4.x-p3.x);
19     double b1=p2.y-k1*p2.x;
20     double b2=p3.y-k2*p3.x;
21     return (b2-b1)/(k1-k2);
22 }
23 double getans()
24 {
25     int i,j,k;
26     double ans=left,right;
27     double tx,ty;
28     point ql,qr,pl,pr;
29     for(i=0;i<n;i++)
30     for(j=0;j<n;j++)
31     {
32         if(i==j)
33         continue;
34         ql=up[i];
35         qr=down[j];
36         right=left;
37         for(k=0;k<n;k++)
38         {
39             tx=up[k].x;
40             ty=(tx-ql.x)*(qr.y-ql.y)/(qr.x-ql.x)+ql.y;
41             if(ty>down[k].y&&ty<up[k].y||fabs(ty-down[k].y)<eps||fabs(ty-up[k].y)<eps)
42             right=tx;
43             else
44             {
45                 if(k)
46                 {
47                     if(ty<down[k].y)
48                     right=getx(ql,qr,down[k-1],down[k]);
49                     else
50                     right=getx(ql,qr,up[k-1],up[k]);
51                 }
52                 break;
53             }
54         }
55         if(right>ans)
56             ans=right;
57     }
58     return ans;
59 }
60 int main()
61 {
62     int i,j,k;
63     while(scanf("%d",&n)&&n)
64     {
65         for(i=0;i<n;i++)
66         {
67             scanf("%lf%lf",&up[i].x,&up[i].y);
68             down[i]=up[i];
69             down[i].y-=1.0;
70         }
71         double ans=getans();
72         if(ans>up[n-1].x||fabs(ans-up[n-1].x)<eps)
73         printf("Through all the pipe.\n");
74         else
75         printf("%.2lf\n",ans);
76     }
77     return 0;
78 }