先做凸包
然後枚舉線段
跟外接三角形的圓
另外ZJ的DATA我覺得有問題
然後枚舉線段
跟外接三角形的圓
另外ZJ的DATA我覺得有問題
- 8月 03 週一 200916:03
NPSC - 2006 B 古力德
- 8月 03 週一 200912:51
PKU - 2139 Six Degrees of Cowvin Bacon
有兩種想法
一種是用MOVIE為關係去畫一個牛之間的相鄰圖
這樣worst case是O(N^2 M) (建表
一種是用MOVIE為關係去畫一個牛之間的相鄰圖
這樣worst case是O(N^2 M) (建表
- 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的範圍我是用比較直觀的大小
標準的Divide and conquer
有數學式證明只需要檢查該點Y排序好的上下共七點即可
然後restrict的範圍我是用比較直觀的大小
- 8月 01 週六 200914:25
ACM 218 - Moth Eradication
一題很單純的求凸包
http://nopaste.csie.org/c7023
http://nopaste.csie.org/c7023
- 8月 01 週六 200911:01
ACM 109 - SCUD Busters
沒想出特別的算法來確定飛彈是不是打到王國內
因此就只能重新做新凸包
然後確定該點是不是新凸包的Boundary
因此就只能重新做新凸包
然後確定該點是不是新凸包的Boundary
- 8月 01 週六 200908:17
Bokura no bouken
http://www.youtube.com/watch?v=xQLlGzJXu7c&NR=1
羅馬拼音
Doko ni aru no ka na Boku dake no takaramono
Ima Ooki na bouken e
Shinkokyuu Yume no tobira ni sotto te o kakete... "Yukou!"
Kaze ni fukare nagara Kokoro yurashi nagara
Masshiro na chizu o katate ni mochi nagara
Boku wa hashiridasu yo Yume o kanaeru tame
Donna kabe mo koete yaru
Kaze ni fukare nagara Asu o kaki nagara
Tooku made Doko made? Yukeru tokoro made
Tanjun na fuan mo fukuzatsu na mirai mo
Mou Nani mo nani mo Kowakunai
Yukkuri sagaseba ii Kizutsuku koto nante sore wa minna onaji da yo...
Kake dashita boku wa "Yume no tabibito" sa
Sora mo hana mo hora waratte iru
Tatta hitotsu no sou Jibun no michi
Kutsu no himo o musubu mae kara Akiramechaikenai... "Dakara!"
Kaze ni fukare nagara Kokoro yurashi nagara
Masshiro na chizu o katate ni mochi nagara
Kaze ni fukare nagara Asu o kaki nagara
Tooku made Doko made? Tadori tsukeru made
Zettai makenai yo Zettai nakanai yo
Kono yume o kanaeru sono hi made wa
Ano sora wa waratte ita Ano hana wa waratte ita
Boku mo itsu ka warau kara
Donna kabe mo koeru kara
Mou Nani mo nani mo... Kowakunai
羅馬拼音
Doko ni aru no ka na Boku dake no takaramono
Ima Ooki na bouken e
Shinkokyuu Yume no tobira ni sotto te o kakete... "Yukou!"
Kaze ni fukare nagara Kokoro yurashi nagara
Masshiro na chizu o katate ni mochi nagara
Boku wa hashiridasu yo Yume o kanaeru tame
Donna kabe mo koete yaru
Kaze ni fukare nagara Asu o kaki nagara
Tooku made Doko made? Yukeru tokoro made
Tanjun na fuan mo fukuzatsu na mirai mo
Mou Nani mo nani mo Kowakunai
Yukkuri sagaseba ii Kizutsuku koto nante sore wa minna onaji da yo...
Kake dashita boku wa "Yume no tabibito" sa
Sora mo hana mo hora waratte iru
Tatta hitotsu no sou Jibun no michi
Kutsu no himo o musubu mae kara Akiramechaikenai... "Dakara!"
Kaze ni fukare nagara Kokoro yurashi nagara
Masshiro na chizu o katate ni mochi nagara
Kaze ni fukare nagara Asu o kaki nagara
Tooku made Doko made? Tadori tsukeru made
Zettai makenai yo Zettai nakanai yo
Kono yume o kanaeru sono hi made wa
Ano sora wa waratte ita Ano hana wa waratte ita
Boku mo itsu ka warau kara
Donna kabe mo koeru kara
Mou Nani mo nani mo... Kowakunai
- 7月 31 週五 200917:33
ACM 10298 - Power Strings
之前做過 後來發現應該用KMP實做
只要先算好Prefix
就可以知道真正"可能"長度
再來去Check 就知道是不是a^n了
只要先算好Prefix
就可以知道真正"可能"長度
再來去Check 就知道是不是a^n了
- 7月 31 週五 200915:07
ACM 11475 - Extend to Palindrome
Reverse原字串然後用KMP去比對
不相等字串B | 相等字串A |
| 相等字串A | 新增字串C
不相等字串B | 相等字串A |
| 相等字串A | 新增字串C
- 7月 30 週四 200921:31
PKU - 3625 Building Roads
蠻標準的一題MST
詳細可見DJWS的文章
http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html
話說我真不知道我之前解MST那算法應該叫做什麼
詳細可見DJWS的文章
http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html
話說我真不知道我之前解MST那算法應該叫做什麼
