先做凸包
然後枚舉線段
跟外接三角形的圓
另外ZJ的DATA我覺得有問題
我當初送出去有特別用SPECIAL處理
這邊我沒有
- 8月 03 週一 200916:03
NPSC - 2006 B 古力德
- 8月 03 週一 200912:51
PKU - 2139 Six Degrees of Cowvin Bacon
有兩種想法
一種是用MOVIE為關係去畫一個牛之間的相鄰圖
這樣worst case是ON2 M 建表
另外是以一個MOVIE為基準 去搜查該MOVIE跟哪些MOVIE相連
做BFS
然後查TABLE找最短DISTANCE
這樣worst case是ON2 M NM 枚舉任兩點 然後用BFS求最
- 8月 03 週一 200911:37
PKU - 2187 Beauty Contest
一開始以為只需要測四個端點即可
後來發現不是
應該要做凸包
然後檢查外圍才對
- 8月 03 週一 200909:14
ACM 10245 - The Closest Pair Problem
The closet pair problem
標準的Divide and conquer
有數學式證明只需要檢查該點Y排序好的上下共七點即可
然後restrict的範圍我是用比較直觀的大小
但也有可能可以更好
- 8月 01 週六 200914:25
ACM 218 - Moth Eradication
一題很單純的求凸包
- 8月 01 週六 200911:01
ACM 109 - SCUD Busters
沒想出特別的算法來確定飛彈是不是打到王國內
因此就只能重新做新凸包
然後確定該點是不是新凸包的Boundary
凸包面積則是用Cross公式運算
- 8月 01 週六 200908:17
Bokura no bouken
羅馬拼音
Doko ni aru no ka na Boku dake no takaramonoIma Ooki na bouken eShinkokyuu Yume no tobira ni sotto te o kakete... Yukou!Kaze ni fukare nagara Kok
- 7月 31 週五 200917:33
ACM 10298 - Power Strings
之前做過 後來發現應該用KMP實做
只要先算好Prefix
就可以知道真正可能長度
再來去Check 就知道是不是an了
反之則一定長度為1
- 7月 31 週五 200915:07
ACM 11475 - Extend to Palindrome
Reverse原字串然後用KMP去比對
不相等字串B 相等字串A
相等字串A 新增字串C
然後看最長可以核對相同到多長的長度
限制條件是他一定是到底的 中間子字串核對相同不算 因為這樣後面會發生碰撞的情形
- 7月 30 週四 200921:31
PKU - 3625 Building Roads
蠻標準的一題MST
詳細可見DJWS的文章
話說我真不知道我之前解MST那算法應該叫做什麼
因為今天看完了這兩種
發現都不是Orz
