> N LOG N 算法怎么来？
> 我加了注释
> #include <stdio.h>
> struct stct0{
>     double x,y;
> }p[40];
> typedef struct stct0 node;
> int convex[2][20],convN[2],topN[2],data[2];
> double outer(node p1,node p2,node p3,node p4){
>     return (p2.x-p1.x)*(p4.y-p3.y)-(p2.y-p1.y)*(p4.x-p3.x);
> }
> int ints(node p1,node p2,node p3,node p4){
>     return outer(p1,p3,p2,p3)*outer(p1,p4,p2,p4)<0&&outer(p3,p1,p4,p1)*outer(p3,p2,p4,p2)<0;//外积 
> }
> double det(double n1,double n2,double n3,double n4){
>     return n1*n4-n2*n3;//行列式 
> }
> double xval(node p1,node p2,node p3,node p4){
>     return det(det(p2.x,p1.x,p2.y,p1.y),det(p4.x,p3.x,p4.y,p3.y),p2.x-p1.x,p4.x-p3.x)/det(p1.y-p2.y,p2.x-p1.x,p3.y-p4.y,p4.x-p3.x);
> //解方程得出直线与直线的交点，我直接一步公式的 
> }
> int tha(node p1,node p2,node p3,node p4,int l){
>     return outer(p2,p1,p3,p2)*outer(p2,p1,p4,p2)<0;
>     //tha="through angle" 表示是否穿越管间结合部的角而穿出管外被挡住 
> }
> int check(int seg,int vtx,int side){
>     //是否合法，仅检验是否会穿过轮廓，需要特别预维护下轮廓两头，以便统一处理 
>     node p1,p2,p3,p4;
>     if((2*convex[1][0]+convex[side][seg]-convex[1-side][vtx])%convex[1][0]==0) return 0;
>     p1=p[convex[1-side][vtx]];
>     p2=p[convex[side][seg]];
>     if(seg==0) p3=p[convex[side][0]],p3.y+=1-2*side;
>     else p3=p[convex[side][seg-1]];
>     if(seg==convN[side]) p4=p[convex[side][convN[side]]],p4.y+=1-2*side;
>     //side 表示识别上下轮廓谁是前基谁是后基 
>     else p4=p[convex[side][seg+1]];
>     if(tha(p1,p2,p3,p4,side)) return 0;
>     p2=p[convex[1-side][vtx]];
>     p1=p[convex[side][seg]];
>     if(vtx==0) p4=p[convex[1-side][0]],p4.y-=1-2*side;
>     else p4=p[convex[1-side][vtx-1]];
>     if(vtx==convN[1-side]) p3=p[convex[1-side][convN[1-side]]],p3.y-=1-2*side;
>     else p3=p[convex[1-side][vtx+1]];
>     if(tha(p1,p2,p3,p4,side)) return 0;
>     return 1;
> }
> int main(){
>     int n,i,dest,seg,vtx,l,flag,j,fail,lb,rb,mb;
>     int pp,qq;
>     double best,tmpv;
>     while(scanf("%d",&n),n){
>         for(i=0;i<n;i++){
>             scanf("%lf%lf",&p[i].x,&p[i].y);
>             p[i+n]=p[i],p[i+n].y-=1;
>         }
>         convN[0]=0;
>         convN[1]=0;
>         convex[0][0]=0;
>         convex[1][0]=n;
>         for(i=1;i<n;i++){//动态维护上下凸轮廓 ，扩增顶点 
>             topN[0]=convN[0],topN[1]=convN[1];
>             while(convN[0]&&outer(p[i],p[convex[0][convN[0]]],p[convex[0][convN[0]-1]],p[convex[0][convN[0]]])<=0)
>                 convN[0]--;
>             while(convN[1]&&outer(p[i+n],p[convex[1][convN[1]]],p[convex[1][convN[1]-1]],p[convex[1][convN[1]]])>=0)
>                 convN[1]--;
>             data[0]=convex[0][convN[0]+1];
>             data[1]=convex[1][convN[1]+1];
>             convex[0][++convN[0]]=i;
>             convex[1][++convN[1]]=i+n;
>             fail=0;
>             for(l=0;l<=1;l++){//利用凸轮廓斜率单调性2分检验当前凸轮廓是否会相交 ， l=0,1分别表示上壳前基下壳后基与下壳前基上壳后基 
>                 lb=1,rb=convN[1-l];
>                 while(lb<rb){
>                     mb=(lb+rb+1)/2;
>                     tmpv=outer(p[convex[1-l][mb]],p[convex[1-l][mb-1]],p[convex[l][convN[l]-1]],p[convex[l][convN[l]]]);
>                     if((l==0&&tmpv>0)||(l==1&&tmpv<0)) lb=mb;
>                     else rb=mb-1;    
>                 }
>                 if(ints(p[convex[l][convN[l]-1]],p[convex[l][convN[l]]],p[convex[1-l][lb]],p[convex[1-l][convN[1-l]]])){
>                     convex[0][convN[0]]=data[0];
>                     convex[1][convN[1]]=data[1];
>                     convN[0]=topN[0];
>                     convN[1]=topN[1];
>                     fail=1;//相交了 
>                     break;
>                 }
>             }
>             if(fail) break;//相交就不用在扩增顶点（管）对了 
>         }
>         if(i==n){
>             printf("Through all the pipe.\n");//射通了 
>             continue;
>         }else dest=i;//destination 记录下最终能到达的管子是哪段 
>         best=p[0].x;
>         for(l=0;l<=1;l++){//同样以上下壳分别做前后基，线性扫描 
>             seg=convN[l];//后基，用以检验是否穿越此轮廓 
>             vtx=convN[1-l];//前基，光线以该点尝试各种角度射出 
>             while(~vtx){
>                 while(1){//退后基，不检验是因为根本不合法或不可能比当前值优 
>                     tmpv=outer(p[convex[1-l][vtx]],p[convex[l][seg-1]],p[convex[1-l][vtx]],p[convex[l][seg]]);
>                     if((l==0&&tmpv>0)||(l==1&&tmpv<0)) seg--;
>                     else break;
>                 }
>                 if(check(seg,vtx,l)){//分别检验两侧光线 
>                     tmpv=xval(p[convex[l][seg]],p[convex[1-l][vtx]],p[dest-1],p[dest]);
>                     if(tmpv>best){
>                         best=tmpv;
>                         pp=convex[l][seg],qq=convex[1-l][vtx];
>                     }
>                     tmpv=xval(p[convex[l][seg]],p[convex[1-l][vtx]],p[dest-1+n],p[dest+n]);
>                     if(tmpv>best){
>                         best=tmpv;
>                         pp=convex[l][seg],qq=convex[1-l][vtx];
>                     }
>                 }
>                 vtx--;//检验完当前点对退前基后继续检验 
>             }
>         }
>         /*
>         一个结论：如果凸轮廓处理时不要平行的线段，即线段斜率严格凸，斜率的倒数严格单调，
>         那么一个前基严格只能和一个后基形成合法匹配，其他的直接都要穿越轮廓，
>         所以找到合法的以后，立刻退掉前基，因为不可能再有第2个后基和他匹配了
>         若维护轮廓时只是非严格单调，即相邻线段斜率可取等号，
>         那么由扫描顺序可知以后必不会更优，也无必要再扫 ，还是可以退掉前基 
>         */
>         printf("%.2lf\n",best);
>     }   
>     return 0;
> }