poj 1039 Pipe （计算几何）

题目：http://poj.org/problem?id=1039

刘汝佳的黑书《算法艺术与信息学竞赛》上的第3章计算几何初步的例2 管道问题

有一宽度为1的折线管道,上面顶点为(xi,yi),所对应的下面顶点为(xi,yi-1),假设管道都是不透明的,不反射的,光线从左边入口处的(x1,y1),(x1,y1-1)之间射入,向四面八方传播,求解光线最远能传播到哪里(取x坐标)或者是否能穿透整个管道.

思路：首先，一根光纤自始至终未曾擦到任何顶点，肯定不是最优的（可以平移使之优化），然后，如果只碰到一个顶点，那也不是最优的，可以通过旋转，是他碰到另一个顶点，并且更优，最后要说明，最优光线必然是擦到一个上顶点，一个下顶点。。。。

任取一个上顶点一个下顶点形成直线L，然后从左到右依次判断管壁与其相不相交，若相交停止循环找出交点与之前的交点比较，找到最大的x即可，若一直都不想交则就是L射穿了整个管道。。。

代码：

View Code

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 using namespace std;
  5 typedef struct node
  6 {
  7     double x,y;
  8 }point;
  9 point up[31];
 10 point down[31];
 11 const double eps=1e-8;
 12 const double inf=99999.0;
 13 int max(int a,int b)
 14 {
 15     if(a>b)
 16     return a;
 17     else
 18     return b;
 19 }
 20 int dblcmp(double d)//浮点误差的处理
 21 {
 22     if(fabs(d)<eps)
 23     return 0;
 24     return (d>0)?1:-1;
 25 }
 26 double det (double x1,double y1,double x2,double y2)//叉乘
 27 {
 28     return x1*y2-x2*y1;
 29 }
 30 
 31 double cross(point a,point b,point c)
 32 {
 33     return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);//向量
 34 }
 35 
 36 int pan(point a,point b,point c,point d)
 37 {
 38     return (dblcmp(cross(a,b,c))*dblcmp(cross(a,b,d))<=0);//规范相交和与顶点相交的两种不规范相交
 39 }
 40 
 41 double get_x(point a,point b,point c,point d)//求交点
 42 {
 43     double area1=cross(a,b,c);
 44     double area2=cross(a,b,d);
 45     int d1=dblcmp(area1);
 46     int d2=dblcmp(area2);
 47     if(d1*d2<0)
 48     return (area2*c.x-area1*d.x)/(area2-area1);//规范相交的交点公式
 49     if(d1*d2==0)
 50     {
 51         if(d1==0)//交于第k-1个点
 52         return c.x;
 53         else//交于第k个点
 54         return d.x;
 55     }
 56     return -inf;//不相交
 57 }
 58 int main()
 59 {
 60     int n;
 61     while(scanf("%d",&n)!=EOF)
 62     {
 63         if(n==0)
 64         break;
 65         int i,j;
 66         for(i=0;i<n;i++)
 67         {
 68             scanf("%lf%lf",&up[i].x,&up[i].y);
 69             down[i].x=up[i].x;
 70             down[i].y=up[i].y-1;
 71         }
 72         //依次枚举每个点
 73         int flag=0;
 74         double res=-inf;//初始化为最小负数,因为坐标可能为负的
 75         int k;
 76         for(i=0;i<n;i++)
 77         {
 78             for(j=0;j<n;j++)
 79             {
 80                 if(i==j)
 81                 continue;
 82                 for(k=0;k<n;k++)
 83                 {
 84                     if(!pan(up[i],down[j],up[k],down[k]))//判断直线L能否穿过k点的管道
 85                     break;
 86                 }
 87                 if(k>=n)//穿过全部的管道
 88                 {
 89                     flag=1;
 90                     break;
 91                 }
 92                 else
 93                 {
 94                     if(k>max(i,j))
 95                     {
 96                         double uu=get_x(up[i],down[j],up[k-1],up[k]);//与上管壁相交的情况
 97                         if(res<uu)
 98                         res=uu;
 99                         uu=get_x(up[i],down[j],down[k-1],down[k]);//与下管壁相交的情况
100                         if(res<uu)
101                         res=uu;
102                     }
103 
104                 }
105             }
106             if(flag)
107             break;
108         }
109         if(flag==1)
110         printf("Through all the pipe.\n");
111         else
112         printf("%.2f\n",res);
113     }
114     return 0;
115 }