给定一个内含阻碍墙的房间,你要编程找到一条从起点到终点的最短路。
判断线段相交的题目
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int n_max=105; const int inf=1<<30; const double precision=1e-6; struct point { double x,y; void add(double tx,double ty) { x=tx; y=ty; } }p[n_max]; struct wall { point low,hig; void add(double x1,double y1,double x2,double y2) { low.add(x1,y1); hig.add(x2,y2); } }w[n_max]; int np,nw; int poi[n_max][n_max]; int wal[n_max][n_max]; double d[n_max]; void init() { int i; for(i=0;i<n_max;i++) { poi[i][0]=0; wal[i][0]=0; } np=0; nw=0; p[np].add((double)0,(double)5); poi[0][++poi[0][0]]=np; d[np++]=0; } void addpoint(int i,double x,double y) { p[np].add(x,y); poi[i][ ++poi[i][0] ] = np; d[np++]=inf; } void addwall(int i,double x1,double y1,double x2,double y2) { if(x1==x2&&y1==y2) { return ; } w[nw].add(x1,y1,x2,y2); wal[i][ ++wal[i][0] ] = nw++; } double dist(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int dblcmp(double d) { if(fabs(d)<precision) { return 0; } return (d>0)?1:-1; } double det(double x1,double y1,double x2,double y2) { return x1*y2 - x2*y1; } double cross(point a,point b,point c) { return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y); } bool segcross(point a,point b,point c,point d) //判断线段是否相交 { return ( dblcmp(cross(a,c,d)) ^ dblcmp(cross(b,c,d)) ) == -2 && (dblcmp(cross(c,a,b)) ^ dblcmp(cross(d,a,b)) ) == -2; } bool judge(int i,int pi,int j,int pj) { int k,u,v,pk,c; v=poi[i][pi]; u=poi[j][pj]; for(k=j+1;k<i;k++) { for(pk=1;pk<=wal[k][0];pk++) { c=wal[k][pk]; if(segcross(p[u],p[v],w[c].low,w[c].hig)) { return false; } } } return true; } int main() { int n; while(~scanf("%d",&n),n!=-1) { init(); int i,j,pi,pj; double x,y1,y2,y3,y4; for(i=1;i<=n;i++) { scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4); addpoint(i,x,y1); addpoint(i,x,y2); addpoint(i,x,y3); addpoint(i,x,y4); addwall(i,x,0,x,y1); addwall(i,x,y2,x,y3); addwall(i,x,y4,x,10); } addpoint(n+1,10,5); int u,v; for(i=1;i<=n+1;i++) { for(j=0;j<i;j++) { for(pi=1;pi<=poi[i][0];pi++) { for(pj=1;pj<=poi[j][0];pj++) { if(judge(i,pi,j,pj)) { v=poi[i][pi]; u=poi[j][pj]; d[v] = min(d[v], d[u]+dist(p[u],p[v]) ); } } } } } u=poi[n+1][1]; printf("%.2lf\n",d[u]); } return 0; }