随笔-20  评论-16  文章-36  trackbacks-0

         队友都不肯看计算几何,只好我瞅瞅了……
         黑书上第一个例题,The Doors,思路:把每个门的两点看成图中的一个点,构造一个以两点距离为权值的图(如果不可直达,记为INF),再用dijkstra算法求出两个端点点的最短路。关键在于构图,我的思路是对于每面墙i上的四个点,它与下一面墙i+1上四个点一定是直接可达的,把它们的距离加入dist矩阵,再判断它们与左端点和右端点是否可达,如果可达算出距离,再判断它们与i+2~n面墙上的四个点是否可达,如果可达算出距离。判断可达的方法是黑书的方法。下面是实验的代码:

#include <iostream>
#include 
<cmath>
#define eps 1e-8
#define inf 100000000
using namespace std;

struct Wall{
    
double x;
    
double y[6];
}
wall[20];
double dist[80][80];
double xmult(double x0,double y0,double x1,double y1,double x2,double y2){
    
return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
}

int dblcmp( double a ){
    
if( fabs(a)< eps )    return 0;
    
return (a>0)?1:-1;
}

bool Cross( double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3 ){
    
return (dblcmp(xmult(x0,y0,x2,y2,x3,y3))^dblcmp(xmult(x1,y1,x2,y2,x3,y3)))==-2 &&
        (dblcmp(xmult(x2,y2,x0,y0,x1,y1))
^dblcmp(xmult(x3,y3,x0,y0,x1,y1)))==-2;
}

bool Direct( int i, int j, int p, int q ){        //判断从墙i的第j个点到墙p第q个点是否直达
    int k, l;
    
for( k= i+1; k< p; k++ ){
        
for( l= 0; l< 6; l+= 2 )
            
if( Cross(wall[i].x,wall[i].y[j],wall[p].x,wall[p].y[q],
                wall[k].x,wall[k].y[l],wall[k].x,wall[k].y[l
+1]) )
                
return false;
    }

    
return true;
}

inline 
double Dist( double x1, double y1, double x2, double y2 ){
    
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
;
typedef 
double elem_t;
double dijkstra(int n){
    
int v[81],i,j,k;
    
double min[81];
    
for (i=0;i<=n;i++)
        min[i]
=inf,v[i]=0;
    
for (min[0]=0,j=0;j<=n;j++){
        
for (k=-1,i=0;i<=n;i++)
            
if (!v[i]&&(k==-1||min[i]<min[k]))
                k
=i;
        
for (v[k]=1,i=0;i<=n;i++)
            
if (!v[i]&&min[k]+dist[k][i]<min[i])
                min[i]
=min[k]+dist[k][i];
    }

    
return min[n];
}

int main(){
    
int n, i, j, k, l;
    wall[
0].x= 0;
    wall[
0].y[0]= 5;
    
while( scanf("%d",&n) && n!=-1 ){
        
for( i= 0; i<= n*4+1; i++ )
            
for( j= 0; j<= n*4+1; j++ )
                dist[i][j]
= inf;
        wall[n
+1].x= 10;
        wall[n
+1].y[1]= 5;
        
bool con= true;
        
for( i= 1; i<= n; i++ ){
            scanf(
"%lf",&wall[i].x);
            
for( j= 1; j< 5; j++ )
                scanf(
"%lf",&wall[i].y[j]);
            
if( wall[i].y[1]>5 || wall[i].y[4]<5 || wall[i].y[2]<5&&wall[i].y[3]>5 )
                con
= false;
            wall[i].y[
0]= 0;
            wall[i].y[
5]= 10;
        }

        
if( con ){
            puts(
"10.00");
            
continue;
        }

        
for( i= 1; i<= n; i++ ){
            
for( j= 1; j< 5; j++ ){
                
if( i< n )
                    
for( k= 1; k< 5; k++ )
                        dist[i
*4+j-4][i*4+k]= Dist(wall[i].x,wall[i].y[j],wall[i+1].x,wall[i+1].y[k]);
                
if( Direct( 00, i, j ) )
                    dist[
0][i*4+j-4]= Dist(0,5,wall[i].x,wall[i].y[j]);
                
if( Direct( i, j, n+11 ) )
                    dist[i
*4+j-4][n*4+1]= Dist(wall[i].x,wall[i].y[j],10,5);
                
for( k= i+2; k<= n; k++ )
                    
for( l= 1; l< 5; l++ )
                        
if( Direct(i,j,k,l) )    
                            dist[i
*4+j-4][k*4+l-4]= Dist(wall[i].x,wall[i].y[j],wall[k].x,wall[k].y[l]);
            }

        }

        printf(
"%.2lf\n",dijkstra(n*4+1));
    }

    
return 0;
}


posted on 2009-05-20 21:15 古月残辉 阅读(842) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理