质疑数据 为什么相似要错 数据的精度是不是有问题

总相差 0.1

DP

每面墙4个关键点(首尾两个)

则每一个关键点=min{之前的每一个可行关键点+dist(这两个点)}

可行即两点连线与墙的连线在墙的缺口处

可以用定比分点的公式

（我就是那个用相似出事故的~~~~~~~~）

用dijkstra也可以

只是代码比dp长一点^_^

DP

添加两面墙 0 n+1

有一点不太了解

我用解直线方程来判断直线相交的问题AC了

不过有朋友说用相似三角就会有麻烦...

至少推荐 还是解出直线方程吧...

第一眼以为是贪心...

dp或者是dij思路都很容易，但是判断线段相交真的是坑。
之前用相似三角形和定比分点一直20分，怎么改都是20分
后来用叉积判断线段相交，AC了
所以不太清楚下面那些用除法的是怎么过的...

为何使用spfa倒数第二个点死活过不去。。