2013
12-11

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.

【有可能光线早就跑到了管道外面,而你判断的确是没有交点,

#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. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。