※ 引述《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)