摘要: 很簡單的幾何題。直接硬搞即可。
閱讀全文
摘要: Winsock入門
閱讀全文
摘要: Winsock入門
閱讀全文
摘要: 見內
閱讀全文
摘要: 又是一個求多邊形的核的題。
閱讀全文
摘要: :)
閱讀全文
摘要: 先求凸包，然后再用旋轉卡殼方法求解。
具體做法是枚舉三角形的第一個點i，設j = i + 1，k = j + 1。然后做以下操作：
1.計算i，j，k構成的三角形面積a1和i，j，k + 1構成的三角形面積a2，如果a2 < a1，則進行下一步，否則k++，重復此步。
2.記錄此時的三角形面積b，如果b < preb（就是上一個j對應的三角形面積）j++，轉第一步，否則退出。
可以證明這個算法的復雜度為O(n2)。具體實現見代碼。
閱讀全文
摘要: 經典的狀態壓縮DP，《算法藝術與信息學競賽》的例題。f[i][j]表示前i行，最后兩行狀態為二進制數j，嵌入的最多芯片數。第i行到第i+1行用DFS進行狀態轉移。
由于第i+1行只和第i行有關，故可以用滾動數組優化。
閱讀全文
摘要: A O(NM) dynamic programming algorithm is quite apparent after sorting the computers and network interfaces by their coordinates. Furthermore, in any optimized case, for each computer the difference between the the indices of the network interfaces matching to and closest to the computer is never larger than N. So the complexity could be reduced to O(N2)
有很多細節不好考慮，應該是我的水平原因。最后我向updog要了數據才過的。而且代碼寫的不好。將就看一下吧。
閱讀全文
摘要: 其實是初等幾何題。在紙上畫一下就出來了。
閱讀全文