队友都不肯看计算几何，只好我瞅瞅了……
黑书上第一个例题，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( 0, 0, i, j ) )
dist[0][i*4+j-4]= Dist(0,5,wall[i].x,wall[i].y[j]);
if( Direct( i, j, n+1, 1 ) )
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
古月残辉 阅读(844)
评论(0) 编辑 收藏 引用 所属分类:
POJ