有點難懂的一題。

翻譯在這裡 http://hi.baidu.com/hpfdf/item/79158059c07d4313abf6d731 感謝中國人XD。

分為 3 個階段。

1. 連線求答案。

2. 判斷是否閉合。

3. 判斷是否交叉。

------------------------------------------------------

1. Greedy

 

只有以上兩種可能(x同 or y同)。

再加上一個點的兩個邊要夾 90度,所以一定是分別連到 x同 和 y同的點。

若要連到 同x or 同y,必定只能連 最靠近 的那個,否則會讓中間的點不合規定。

這時可以得到一個結論,若有解則僅有唯一解。

照 x排序,把 同x 的兩兩相連起來,若沒有可以配對的則無解。

照 y排序,把 同y 的兩兩相連起來,若沒有可以配對的則無解。

當然要順便把 dis 加起來。

最後就會像下圖那樣。

 

2. Disjoint set

判斷 閉合 也就是 連通,可以直接 dfs  一次。

我是寫 Disjoint set,讓 find(x) 跟 find(1) 比較異同。

3. BIT

最後一步了,也是最難的一步= =。

把 x軸 壓扁,以 y軸 建立一棵 BIT。

 然後一條 掃描線 掃 x軸 過去。

如果有 鉛直連線(就是 x同),就看 連線的那段上 有沒有東西(query),若 有 東西就表示實際連線時會 交叉,當然就不合法。

如果是 水平連線(就是 y同),看是要 加入(左邊) 還是 拔掉(右邊),更新BIT(add)。

掃完一遍後若沒有交叉,就可以開開心心的把答案印出來了。

------------------------------------------------------

實際code時,有很多細節要小心。

圓滿解決這題了~

我的code

http://snipt.org/Baghf1

p.s: code 有把 x,y 離散化。

 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()