調和的靈感

相當有趣的一題....寫程式產生器 用自創的Modified-Permutation Algo (￣▽￣＃)﹏﹏ 第一次寫有點痛苦，過了幾天醞釀過想法後，寫起來很順很快就AC了 距離連號解題剩下最後一題107了..

I have a dream..... 就是....一次AC..... 最好不是渣渣題.... 到底什麼時候才能達成呢？

解題策略 典型的凸包 (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( ) 的判斷函數，現在重寫一遍，感覺比較清爽一些了!

 "you can't add apples and oranges."「你不能把蘋果和橘子加在一起」 --談為什麼需要向量 The central porblem of linear algebra is to solve a system of equations. 線性代數的核心問題就是要解方程組！ It is also common sense: If you put on socks and then shoes, the first to be taken off are the ___. 常識也告訴我們：假如你先穿襪子再穿鞋，那麼脫的時候，首先該脫掉___。 --談為何AB的反矩陣是B -1 A -1 Ax combines the columns of A while x T A T combines the rows of A T Ax線性組合了A的諸行，而x T A T 線性組合了A T 的諸列。 --談為何(AB) T = B T A T 最近看Gilbert Strang寫的『Introduction to Linear Algebra』，Strang教授講法生動，不論是趣味的例子，或者是一句話直搗觀念核心，都常讓我拍案叫絕。 比起補習班名師的講義，研讀起來樂趣大多了。有機會再補上更多句子。

渣渣題三號 判斷點是否在矩形內。在頭腦不清的凌晨三點，犯了一些低級錯誤，還好很快就AC了。 我最近的休閒娛樂就是寫渣渣題....

Buffered加速版 0.020s。看到很多0.000s，這我真的不知道怎麼做了.... 該不會是用組語寫吧...這題用組語寫似乎很簡單....

難題寫多了，來寫渣渣題。AC 0.020秒

解題策略 Some Hints about uVA 104  gits大大說得很清楚，我就不囉唆作法了。 閒聊 苦思良久的UVa 104終於在 gits 幾乎手把手的帶領下寫出來了，了結了多天以來的心中懸念。XDDD稍微變化題，馬上就把我土法煉鋼學會的Floyd-Warshall 打回原型。連F-W要用二維還是三維陣列來建表都搞不清楚，唉，由這題可以知道我的DP/Graph有待磨練。 只有與問題面對面的對決，在測資跟Bug中打滾一番後，才能對Algorithm有更深刻的體會吧。這也是我寫ACM的目的與樂趣所在。不過...這題還是有點心虛阿.....orz 只能說敗給你了Modified Floyd-Warshall，還未夠班....總有一天我要能秒殺這題。

by gits Original Thread http://online-judge.uva.es/board/viewtopic.php?t=7292 Well, I'll assume you understand what the problem asks. You have to find the shortest sequence that yelds a profit (not the one with the greatest profit!). If there is more then one sequence with the same length, any of those is valid. Now, you can't just try with brute force (trying all combinations) because it'll be too slow and you'll get Time Limit Exceeded. However, there's a well known algorithm, Floyd-Warshall, which will find all the shortest paths between every node to the others in just O(n^3) time. You can find more info about F-W in the net. In my previous post I said how you have to change the general F-W algorithm to work for this particular problem... As for floating point errors, most numbers representation isn't totally acurate; for instance, 0.1 is usually stored as 0.10000000000000001. After some operations, the error may influence the final result. Again, sea...