摘要: 很簡單的幾何題。直接硬搞即可。

  閱讀全文      摘要: Winsock入門

  閱讀全文      摘要: Winsock入門

  閱讀全文      摘要: 見內(nèi)

  閱讀全文      摘要: 又是一個求多邊形的核的題。

  閱讀全文      摘要: :)

  閱讀全文      摘要: 先求凸包，然后再用旋轉(zhuǎn)卡殼方法求解。
具體做法是枚舉三角形的第一個點i，設(shè)j = i + 1，k = j + 1。然后做以下操作：
1.計算i，j，k構(gòu)成的三角形面積a1和i，j，k + 1構(gòu)成的三角形面積a2，如果a2 < a1，則進行下一步，否則k++，重復(fù)此步。
2.記錄此時的三角形面積b，如果b < preb（就是上一個j對應(yīng)的三角形面積）j++，轉(zhuǎn)第一步，否則退出。
可以證明這個算法的復(fù)雜度為O(n2)。具體實現(xiàn)見代碼。

  閱讀全文      摘要: 經(jīng)典的狀態(tài)壓縮DP，《算法藝術(shù)與信息學(xué)競賽》的例題。f[i][j]表示前i行，最后兩行狀態(tài)為二進制數(shù)j，嵌入的最多芯片數(shù)。第i行到第i+1行用DFS進行狀態(tài)轉(zhuǎn)移。
由于第i+1行只和第i行有關(guān)，故可以用滾動數(shù)組優(yōu)化。

  閱讀全文      摘要: 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)

有很多細節(jié)不好考慮，應(yīng)該是我的水平原因。最后我向updog要了數(shù)據(jù)才過的。而且代碼寫的不好。將就看一下吧。

  閱讀全文      摘要: 其實是初等幾何題。在紙上畫一下就出來了。

  閱讀全文