POJ 1039-Pipe（计算几何-线段相交、求交点）

妖狐艹你老母 2022-07-11 16:12 243阅读 0赞

Pipe

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;10638</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;3293</td> 
  </tr> 
 </tbody> 
</table>

Description

The GX Light Pipeline Company started to prepare bent pipes for the new transgalactic light pipeline. During the design phase of the new pipe shape the company ran into the problem of determining how far the light can reach inside each component of the pipe. Note that the material which the pipe is made from is not transparent and not light reflecting.  
![pipe.gif][]  
Each pipe component consists of many straight pipes connected tightly together. For the programming purposes, the company developed the description of each component as a sequence of points \[x1; y1\], \[x2; y2\], . . ., \[xn; yn\], where x1 < x2 < . . . xn . These are the upper points of the pipe contour. The bottom points of the pipe contour consist of points with y-coordinate decreased by 1. To each upper point \[xi; yi\] there is a corresponding bottom point \[xi; (yi)-1\] (see picture above). The company wants to find, for each pipe component, the point with maximal x-coordinate that the light will reach. The light is emitted by a segment source with endpoints \[x1; (y1)-1\] and \[x1; y1\] (endpoints are emitting light too). Assume that the light is not bent at the pipe bent points and the bent points do not stop the light beam.

Input

The input file contains several blocks each describing one pipe component. Each block starts with the number of bent points 2 <= n <= 20 on separate line. Each of the next n lines contains a pair of real values xi, yi separated by space. The last block is denoted with n = 0.

Output

The output file contains lines corresponding to blocks in input file. To each block in the input file there is one line in the output file. Each such line contains either a real value, written with precision of two decimal places, or the message Through all the pipe.. The real value is the desired maximal x-coordinate of the point where the light can reach from the source for corresponding pipe component. If this value equals to xn, then the message Through all the pipe. will appear in the output file.

Sample Input

4
    0 1
    2 2
    4 1
    6 4
    6
    0 1
    2 -0.6
    5 -4.45
    7 -5.57
    12 -10.8
    17 -16.55
    0

Sample Output

4.67
    Through all the pipe.

Source

[Central Europe 1995][]

## 题目意思： ##

给出管道上半部分各个拐点处的坐标（x,y），因为管道宽度为1，所以对应下半部分各个拐点处的坐标是（x，y-1）。

有一道光线从管道最左边射入，光线不能穿透管壁也不能拐弯，求解它是否能穿过这个管道，如果不可以，输出到达管中位置的最大横坐标x。

## 解题思路： ##

先根据上下拐点的连线确定光线的入射斜率，枚举其与各个拐点的上下连线是否有交点，因为有交点则说明光线可以穿过该段管道。如果光线能够穿过管道，那么它将穿过每一段管道。

如果不能穿过，在第k节管道处无法穿过，则需要计算最大坐标x：

分别计算与第k-1节管子的上、下管壁相交， 求得最大坐标。

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<iomanip>
    using namespace std;
    #define MAXN 30
    const int INF=1e9;
    const double eps=1e-3;
    struct point
    {
        double x,y;
    };
    int sgn(double p)//对double确定精度
    {
        if(fabs(p)<eps)  return 0;
        return p>0?1:-1;
    }
    double circulation(point a,point b,point c)//计算向量BA、CA的叉积
    {
        return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    }
    double dir(point A,point B,point P)//计算P点在AB的左侧还是右侧（AC与AB的螺旋关系）
    {
        return circulation(A,B,P);
    }
    bool cross(point A,point B,point C,point D)//判断线段AB和CD是否相交
    {
        return (sgn(dir(A,B,C))*sgn(dir(A,B,D))<=0);
    }
    double intersection(point A,point B,point C,point D)//求AB与CD的交点x值
    {
        double area1=dir(A,B,C);
        double area2=dir(A,B,D);
        int c=sgn(area1);
        int d=sgn(area2);
        if(c*d<0) //CD在AB的两侧，规范相交
            return (area2*C.x - area1*D.x)/(area2-area1);//交点计算公式
        if(c*d==0)   //CD的其中一个端点在AB上，不规范相交
        {
            if(c==0)
                return C.x;//C在AB上,返回AB与CD非规范相交时的交点C的横坐标
            else
                return D.x;//D在AB上,返回AB与CD非规范相交时的交点D的横坐标
        }
        return -INF; //CD在AB同侧，无交点,返回负无穷
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n;
        while(cin>>n&&n)//n表示管道的数目
        {
            point p[MAXN],q[MAXN];
            for(int i=0; i<n; i++)
            {
                cin>>p[i].x>>p[i].y;
                q[i].x=p[i].x;
                q[i].y=p[i].y-1;
            }
            bool flag=false;
            double ans=-INF;
            int k;
            for(int i=0; i<n; i++)//枚举每段线段
            {
                for(int j=0; j<n; j++)
                {
                    if(i==j) continue;
                    for(k=0; k<n; k++)//枚举当前光线与第k个拐点处的上下连线是否相交
                        if(!cross(p[i],q[j],p[k],q[k]))//扫描到一个不相交
                            break;
                    if(k>=n)//与每个拐点处都相交
                    {
                        flag=true;
                        break;
                    }
                    else if(k>max(i,j))//不能穿过，求解最大x值
                    {
                        double temp=intersection(p[i],q[j],p[k],p[k-1]);//求交点横坐标
                        if(ans<temp)//与第k-1节管子的上管壁相交
                            ans=temp;
                        temp=intersection(p[i],q[j],q[k],q[k-1]);
                        if(ans<temp)//与第k-1节管子的上管壁相交
                            ans=temp;
                    }
                }
                if(flag)//可穿
                    break;
            }
            if(flag)
                cout<<"Through all the pipe."<<endl;
            else
                cout<<fixed<<setprecision(2)<<ans<<endl;
        }
        return 0;
    }
    /*
    4
    0 1
    2 2
    4 1
    6 4
    6
    0 1
    2 -0.6
    5 -4.45
    7 -5.57
    12 -10.8
    17 -16.55
    0
    */

[pipe.gif]: /images/20220711/18242cca879648259106e6749a2d74c0.png
[Central Europe 1995]: http://poj.org/searchproblem?field=source&key=Central+Europe+1995