首页 > ACM题库 > HDU-杭电 > Hdu 1454 Pipe-解析几何[解题报告] C++
2013
12-11

Hdu 1454 Pipe-解析几何[解题报告] C++

Pipe

问题描述 :

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.

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.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

4.67
Through all the pipe.


题意:

给你一个管道,问是否能有这样一条光线从左到右边完整通过
如果不能完整通过,则输出最远的相交点【x 最大】

算法:直线与线段相交【叉积】

思路:
枚举上下端点成光线所在的直线即可
看是否合法,如果合法:那么再看是否能够通过整个通道
如果不能通过,则输出最远的 X

注意:

判断线段和直线相交时,不能直接用两个叉积的积来判断
【有可能光线早就跑到了管道外面,而你判断的确是没有交点,
最后结果就变成了光线通过了整个通道,但是事实却并不是这样】
所以,必须让光线和挡板【上下端点所成直线】相交,来确定光线确实在管道内

错误思想:

开始想着直线与线段只可能是下图的情况,那么直接用叉积的积判断直线和线段是否相交好了

红色箭头的代表直线 AB,三条黑色线段代表所有的线段与直线 AB的关系【直线可以延伸,所以画一段没有关系】
那么如果是一般的情况,直接用直线和线段相交的代码判断就好了

#include<stdio.h>
#define eps 1e-8
struct point{
    double x,y;
}p[23],left,right,tp;
double a1,b1,c1,a2,b2,c2;
void get_line1(struct point p1,struct point p2)
{
    a1=p1.y-p2.y;
    b1=p2.x-p1.x;
    c1=p1.x*p2.y-p2.x*p1.y;
}
void get_line2(struct point p1,struct point p2)
{
    a2=p1.y-p2.y;
    b2=p2.x-p1.x;
    c2=p1.x*p2.y-p2.x*p1.y;
}
void get_line3(struct point p1,struct point p2)
{
    p1.y--,p2.y--;
    a2=p1.y-p2.y;
    b2=p2.x-p1.x;
    c2=p1.x*p2.y-p2.x*p1.y;
}
double get_intersectx()
{
    double d=a1*b2-a2*b1;
    return (b1*c2-b2*c1)/d;
}
int main()
{
    int i,j,k,n;
    double ans,temp,tmp;

    while(scanf("%d",&n)>0)
    {
        if(!n) break;
        for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
        for(ans=-0xffffff,i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(i==j) continue;
                left=p[i];
                right=p[j]; right.y--;
                get_line1(left,right);
                for(temp=-0xffffff,k=0;k<n;k++)
                {
                    tp.x=p[k].x;
                    tp.y=left.y-(left.x-tp.x)*(right.y-left.y)/(right.x-left.x);
                    if(p[k].y+eps>tp.y&&tp.y>p[k].y-1-eps) temp=p[k].x;
                    else
                    {
                        if(k>0)
                        {
                            if(tp.y>p[k].y) get_line2(p[k-1],p[k]);
                            else get_line3(p[k-1],p[k]);
                            tmp=get_intersectx();
                            if(p[k-1].x-eps<tmp&&tmp<p[k].x+eps) temp=tmp;
                        }
                        break;
                    }
                }
                if(temp>ans) ans=temp;
            }
        }
        if(ans<p[n-1].x) printf("%.2lf\n",ans);
        else printf("Through all the pipe.\n");
    }

    return 0;
}

 


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。