叉积不就是直线方程么，同源同理

........当然用定比分点(和相似有区别吗?),然后用spfa,就过了

终于过了，哈哈哈

叉积.......

庆祝第300个AC的

第 N 个一次 AC 的 ( N 接近 300, 因为都是牛人)

可以简单地用DP思想

每次分析一堵强的其中一个点时，跟前面所有墙的的4个点（略写了）和出发点连线，判断这些线是否经过了任何墙，如果没有经过，则记录p为该带到目标点的距离与原先记录的目标点的最短距离之和。再判断p是否小于该点的当前最短距离。是则交换

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

floyed+直线解析式

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

---|---|---|---|---|---|---|---|---|--

不会叉积，用直线方程一样过

相似三角形+Dijkstra

第一组数据MS有问题，a1,b1,a2,b2不是递增的8.80 1.00 3.00 5.00 4.00

最短路嘛.但怎么用计算几何呢?

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Accepted 有效得分：100 有效耗时：0ms

汗……一开始把法向量的x,y不小心颠了个倒，竟然还能碰对一个点

我是这样判断：

通过计算直线 起点到 墙上开口的两个端点 的向量 在直线法向量上的投影 的符号是否相反 来确定是否被某段墙挡住

（举个例），起点到(7,4.5)的直线l 法向量n=(0.07,1)，那么，起点到(4,7)和(4,2)的向量 在n上的投影的符号必然相反，即乘积0）

这样不用求直线方程

然后和别人一样，DP

我用解函数解析式过的

看了楼下的，结果一头雾水

才疏学浅　不知什么是叉积　请高手解释

叉乘+DP。。。

可以想到，路线最短要不是可以直接沿直线通过，要不就要走一条通过若干个墙角的折线。可以把每一个缺口的上下两点抽象成图中的两个节点，使用叉积计算判断出各个点之间的连通性以及距离，之后对这个构造出来的图求解从原点到汇点的最短路即可。

我用相似三角形也有问题，第4组会出现误差

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

用一个简单的叉积判断是否相交，从后向前DP就行

把check(i,j,k,l) and ((dist+len(x[i],y,x[k],y[k,l])

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

三重循环的暴力枚举来建立图

三重循的Floyd硬来

叉积+DP或者叉积+Dijkstra或者定比分点法都行.

这个，虽然是一次AC，但是是先看了题解的。革命尚未成功，本同志需继续努力啊。