※ 引述《chchwy (mat)》之铭言： : 9. Greedy解 : 我想看看要怎麽写比较简洁清楚..... 这题我没想到比较完整的解法 有请建中哥解说~~ : 10. no idea....? : O(nlogn+I)....找资料中= =" 暴力解 就是用点斜式去带 而且这题已经很简单的改成只有"水平"跟"垂直" 所以也不用算斜率了 比较xy座标就知道他是水平或垂直 而且水平只会跟垂直相交 反之亦然 另外一种解法是用向量外积判断点是在线段的左方或右方。 给定两线段 a-b, c-d，用ab 表示由 a 至 b 的向量。 首先检查 c 落在 ab 的哪个方向，接着检查 d， 若是两着落在 ab 不同的两方，则表示 c-d 与 a-b 所"延长的直线"有相交。 因此反过来再判断 a,b 是否也落在 cd 的两边， 即可得知两线段是否有相交。 PS.非常遗憾 我比赛时间还在推最小公因数跟外积的公式 最小公因数有推出来 外积还是想不起来 >"< ※ 编辑: cair 来自: 203.68.15.217 (11/29 02:00)