UVa 109 SCUD Busters

解題策略

典型的凸包 (Convex Hull ) 問題。我是採用 Graham's Scan 來解。作法可以參考維基條目 Graham's Scan，我就是照著條目裡的算法原封不動實做的。

本題要找出所有被飛彈摧毀的王國的國土面積總和。過程中一共有兩件事要解決，第一個要知道每個王國的國土面積，第二個要能判斷飛彈落點有沒有打中王國。

求國土面積，要先對王國內的所有的發電廠位置求凸包，然後由凸包去計算多邊形面積 (題目頁有給多邊形面積公式) 。 判斷飛彈落點是否落在國土內，也是以凸包為基礎，沿著凸包的每個邊判斷，如果飛彈落點都在邊的左側，那就表示打中了!

注意

使用Graham's Scan 時要特別注意共線問題，尤其是起始點三點共線，例如 (0,0) (1,1) (2,2) (1,3) ，求出來的凸包應該是 (0,0) (2,2) (1,3)。

閒聊

@2011.10.07
有點囉嗦的題目。2008年底我第一次解這題，因為過程有點曲折，所以花了好幾天才解出來，而且一直搞不定 std::sort( ) 的判斷函數，現在重寫一遍，感覺比較清爽一些了!

留言

  1. 匿名2009年2月3日 凌晨3:39

    try this?

    bool cmp( const Point &a, const Point &b )

    回覆刪除
  2. chchwy2009年2月14日 上午9:59

    我相信我應該試過..
    bool cmp( const Point &a, const Point &b )

    不過有空的時候再重新檢查一次好了...等我有空orz

    回覆刪除

張貼留言

這個網誌中的熱門文章

UVa 10125 Sumsets

解題策略 這題的解法很直接，要找d=a+b+c 用四層迴圈下去跑a,b,c,d就好了 XDDDD 我犯了幾個錯誤 要找最大符合d (意思是數列中可能出現好幾個符合要求的解)，所以迴圈應該由最大元素往下找，第一個找到的解就是答案，我一開始由最小元素往上遞增尋找，拿了WA。 沒找到解就回傳0，殊不知0也有可能是解: 0 = -5 + 3 + 2，這裡也吃了一個WA，所以我後來改回傳 INT_MAX 作為無解。 這題有負值，所以 -5 = -10 + -2 + 7 ，這樣算一組合法的解。 是比較需要小心的地方。 官網論壇上的(a+b)=(d-c)法，方法複雜很多，卻沒有比較快。
閱讀完整內容

讀書心得: 撒哈拉的故事

圖片
初拿起「撒哈拉的故事」時，我心中想著大概是本以沙漠為背景的美麗幻想般的愛情小說吧，有誰會真的費盡千辛萬苦跑去撒哈拉沙漠，在物質極為缺乏的環境下過著刻苦的生活呢? 沒想到這人就是三毛，只因為一個理由「我要認識沙漠」。 「撒哈拉的故事」是三毛與她的丈夫荷西在撒哈拉沙漠旅遊生活的紀實，生活在沙漠很糟糕，至少我看完最後一篇『白手成家』後認為實在很糟，不過在樂觀又開朗的三毛的筆下，撒哈拉沙漠化為一個有趣又不可思議的國度，說著一個又一個異國的故事。 如果不是三毛，我無法想像原來世界上還有這樣子的一群人，還有這等事情，你能想像沙哈拉威人三四年才洗一次澡嗎? 『觀浴記』裡三毛跑去看沙漠女人洗澡，要先用蒸氣蒸，再用石片刮下身上的泥沙，而且沙漠女人不只洗外面，還洗裡面，讓我看的哈哈大笑。『娃娃新娘』 裡則是三毛的一個沙哈拉威鄰居叫「姑卡」要出嫁了，可是她才十歲呀，結婚習俗更是特別，新郎去迎接新娘時，新娘拼命的抵抗，原來才在沙哈拉威人的觀念裡，打得激烈才叫做「好女人」，不掙扎事後會被取笑的。 沙哈拉威人很少受教育，思想沒有邏輯，通常講道理是講不通的。有次三毛要參加晚宴，遍尋不著自己的漂亮高跟鞋，反倒是鞋櫃上多了一雙破鞋子，原來高跟鞋被鄰居小女孩偷去穿了。事後三毛很生氣地跟她理論，小女孩竟然回嘴「生氣，生氣，你的鞋子在我家，我的鞋子還不是在你家，我比你還要氣。」聽見這種話真的是秀才遇到兵，有理講不清，還好三毛是個灑脫的人，笑笑就過去了。 事實上，生活在沙漠真的需要灑脫，老是計較小事肯定活不下去。除了講不清道理的沙拉哈威鄰居，沙漠也有許多危險，書中至少有兩次三毛差點在沙漠裡丟掉小命。但是每一篇故事裡，我都看見一位勇氣可嘉的中國女孩兒，她不屈不撓，以樂觀的心和智慧面對生活中的困難，盡情的玩，盡情的享受生活，像個瘋狂的孩子般，最後甚至布置了一個號稱撒哈拉沙漠裡最美麗的家，連記者都聞風專程前來拜訪，他們的物質生活雖不富裕，但是精神卻很富足。 說到三毛不能不提她的另一半荷西。三毛書裡這樣子描寫『荷西有一個很大的優點，任何三毛所做的事情，在別人看來也許是瘋狂的行為，在他看來卻是理所當然的』，所以當三毛說要去沙漠時，荷西早她兩個月，就先對著撒哈拉沙漠找工作去了，沙漠裡的瘋狂事也總有荷西的一份。人生能遇見這樣的他，既是羨慕，也是感動。
閱讀完整內容

讀書心得: 你以為你以為的就是你以為的嗎?

圖片
當初想要接觸哲學的時候，挑上的第一本書就是「你以為你以為就是你以為的嗎?」，因為書名太好玩了。讀完後發現內容也一樣好玩，整本書的形式有點像坊間流行的心理測驗小書，每章的開頭都要讀者先做一組題目，後面接著就對你的答案做一番分析。 我自己的讀後感是，恩，這些題目對一個以前從未接觸過哲學的人來說太過犀利，第一次作答的時候，每翻過一頁都好像在呼自己巴掌，臉頰很燙。 「你以為你以為就是你以為的嗎?」書名念起來很拗口，但是很貼切，因為這些題目為的是要檢查我們腦袋內的想法是否一致，在邏輯上有沒有BUG。 我舉個例子，書裡有道題目「只要不傷害他人，任何人都有權自由追求自己的目標」要讀者回答同不同意，我認為這句話聽起來相當合理，所以勾了同意。過了幾題後，出現另一道題目是「為個人吸食而持有毒品的行為應予除罪化」，這次我的直覺是毒品這麼危險，怎麼可以除罪化呢，馬上勾不同意。 但是，我沒有發現這是刻意安排的陷阱，因為這兩句話其實講的是同一回事。 單純個人持有毒品，不散佈也不販賣，就不算傷害他人，那他就應該有自由追求自己的「吸食毒品」目標的權利，畢竟他只有傷害自己呀。這敘述聽起來有點危險，不過我必須承認一開始的確想的不夠清楚，我以為第一句話是真理，但馬上被反例打了自己的臉。 再舉一個例子，首先是「對藝術品的評斷，純粹是個人品味的問題」，接著是「米開朗基羅是史上數一數二的偉大藝術家」，這牽涉到評斷藝術的標準，不過你只能認同兩句話的其中之一。 書中我最有興趣的是「神明DIY工作室」與「信仰殺戮戰場」，這兩章擺明了直衝基督徒而來。當中有些問題圍繞著以下的敘述，如果你同意「神是全知、全能、又全然慈愛」，那該怎麼解釋世界上發生的許多苦難呢? 比如說被南亞海嘯淹沒的小女孩? 如果神沒辦法消除這些苦難，祂就不是全能。如果神沒辦法事先知道創造出來的世界會有這些苦難，祂就不是全知。如果神明知道有苦難，也有能力去掉，但是卻故意不做，那祂就不是全然慈愛。 我思考後的結論是，全然慈愛的神並不等於神希望世上的苦難越少越好，這些苦難都是在祂的允許下發生的。 書裡指出了一個基督徒的通病，被問倒了之後就嚷嚷「你不知道神是超越人所理解的嗎 」，但回頭又馬上賦予神非常明確地人的屬性。後來我也理解到這些尖銳的問題並不是故意要為難我對神的看法，而是逼迫我去反思一些比較深層的宗教議題，就像我...
閱讀完整內容