UVa 393 The Doors

题目描述你需要找到穿过一个有障碍墙的房间的最短路径长度。房间边界为x0x0x0、x10x10x10、y0y0y0和y10y10y10。路径的起点和终点始终是(0,5)(0,5)(0,5)和(10,5)(10,5)(10,5)。房间内有000到181818堵垂直的墙每堵墙上有两个门洞。图例展示了一个这样的房间以及最短路径。输入格式第一行包含内墙的数量nnn。接下来nnn行每行包含五个实数第一个数是墙的xxx坐标0x100 x 100x10其余四个是墙上两个门洞端点的yyy坐标。墙的xxx坐标递增排列每行内的yyy坐标也递增排列。输入以n−1n -1n−1结束。输出格式对于每个房间输出一行包含最短路径长度保留两位小数无空格。样例输入1 5 4 6 7 8 2 4 2 7 8 9 7 3 4.5 6 7 -1样例输出10.00 10.06题目分析问题的本质这是一个带障碍的最短路径问题。房间内有若干垂直墙每堵墙上有两个门洞开口。需要从(0,5)(0,5)(0,5)走到(10,5)(10,5)(10,5)不能穿过墙的实体部分只能从门洞通过。几何建模将起点、终点、所有墙上门洞的端点视为图中的节点如果两个节点之间的线段不与任何墙的实体部分相交则它们之间有一条边边的权重为两点间的欧氏距离使用Dijkstra\texttt{Dijkstra}Dijkstra算法求最短路径关键点墙的实体部分由[0,y1][0, y_1][0,y1​]、[y2,y3][y_2, y_3][y2​,y3​]、[y4,10][y_4, 10][y4​,10]组成门洞在(y1,y2)(y_1, y_2)(y1​,y2​)和(y3,y4)(y_3, y_4)(y3​,y4​)需要检查线段是否与墙的实体部分相交即是否穿过墙起点(0,5)(0,5)(0,5)终点(10,5)(10,5)(10,5)参考代码// The Doors// UVa ID: 393// Verdict: Accepted// Submission Date: 2016-07-04// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleEPSILON1E-10;structpoint{doublex,y;intwall;// 所属墙编号0 为起点n1 为终点boolis_valid;};structline{doublea,b,c;// ax by c 0};structedge{intto;doubleweight;};// 两点转直线linepointsToLine(point start,point end){line lr;if(fabs(start.x-end.x)EPSILON){lr.a1.0;lr.b0.0;lr.c-start.x;}else{lr.a-(start.y-end.y)/(start.x-end.x);lr.b1.0;lr.c-lr.a*start.x-start.y;}returnlr;}// 计算直线在给定 x 处的 y 值doublegetYAtLine(line lr,doublex){return(-lr.c-lr.a*x)/lr.b;}// 判断两条直线是否平行boolisParallelLine(line line1,line line2){returnfabs(line1.a-line2.a)EPSILONfabs(line1.b-line2.b)EPSILON;}// 判断两条直线是否重合boolisSameLine(line line1,line line2){returnisParallelLine(line1,line2)fabs(line1.c-line2.c)EPSILON;}// 求两直线交点pointintersect(line line1,line line2){point p;if(isParallelLine(line1,line2)){return{0.0,0.0,false};}if(isSameLine(line1,line2)){if(fabs(line1.a)EPSILON){p.x-line1.c/line1.a;p.y0.0;}else{p.x0.0;p.y-line1.c/line1.b;}p.is_validtrue;returnp;}p.x(line2.b*line1.c-line1.b*line2.c)/(line2.a*line1.b-line1.a*line2.b);if(fabs(line1.b)EPSILON)p.y-(line1.a*p.xline1.c)/line1.b;elsep.y-(line2.a*p.xline2.c)/line2.b;p.is_validtrue;returnp;}// 包围盒测试boolpointInBox(point p,point a,point b){return(p.xmin(a.x,b.x)-EPSILONp.xmax(a.x,b.x)EPSILONp.ymin(a.y,b.y)-EPSILONp.ymax(a.y,b.y)EPSILON);}// 判断两点间线段是否与墙的实体部分相交boolsegmentClear(pointa,pointb,mapint,doublewalls,mapint,vectorpairdouble,doubledoors){if(a.wallb.wall)returnfalse;// 相邻墙可直接连接if(b.walla.wall1)returntrue;line lrpointsToLine(a,b);for(intka.wall1;kb.wall-1;k){doubleygetYAtLine(lr,walls[k]);boolinDoorfalse;for(autodoor:doors[k]){if(ydoor.firstEPSILONydoor.second-EPSILON){inDoortrue;break;}}if(!inDoor)returnfalse;}returntrue;}doubledistanceOfPoints(pointa,pointb){returnsqrt(pow(a.x-b.x,2)pow(a.y-b.y,2));}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn;while(cinn,n0){// 无墙的情况if(n0){cout10.00endl;continue;}mapint,doublewalls;mapint,vectorpairdouble,doubledoors;vectorpointpoints;points.push_back({0.0,5.0,0,false});// 起点// 读取墙并构建节点for(inti1;in;i){doublex,y1,y2,y3,y4;cinxy1y2y3y4;walls[i]x;doors[i]{{y1,y2},{y3,y4}};// 四个门洞端点points.push_back({x,y1,i,false});points.push_back({x,y2,i,false});points.push_back({x,y3,i,false});points.push_back({x,y4,i,false});}points.push_back({10.0,5.0,n1,false});// 终点// 建图vectorvectoredgeedges(points.size());for(inti0;ipoints.size();i){for(intjpoints.size()-1;j0;j--){if(points[j].wallpoints[i].wall)break;if(segmentClear(points[i],points[j],walls,doors)){doubledistdistanceOfPoints(points[i],points[j]);edges[i].push_back({j,dist});edges[j].push_back({i,dist});}}}// Dijkstravectordoubledistances(points.size(),1e9);vectorboolvisited(points.size(),false);distances[0]0;for(intstep0;steppoints.size();step){intcurrent-1;doubleminDist1e9;for(inti0;ipoints.size();i){if(!visited[i]distances[i]minDist){minDistdistances[i];currenti;}}if(current-1)break;visited[current]true;for(autoe:edges[current]){if(!visited[e.to]distances[current]e.weightdistances[e.to]){distances[e.to]distances[current]e.weight;}}}coutfixedsetprecision(2)distances.back()endl;}return0;}