摘要: 強(qiáng)烈推薦此題。半平面交算法的一個(gè)應(yīng)用。
具體做法是，把多邊形的每條邊向內(nèi)平移r單位長度，用這些線段所在直線和原多邊形作半平面交，得到的區(qū)域就是半徑為r的圓放入多邊形的可行域。可以證明這個(gè)區(qū)域一定是凸的，或者退化為一條線段，或一個(gè)點(diǎn)。那么，我們就可以在這個(gè)區(qū)域上求最遠(yuǎn)點(diǎn)對(duì)啦。
我的做法是O(n^2)的。應(yīng)該存在O(nlogn)的做法，因?yàn)槎际峭苟噙呅危看伟肫矫娼恢挥凶疃鄡蓚€(gè)交點(diǎn)，可二分，而最后的求最遠(yuǎn)點(diǎn)對(duì)可以旋轉(zhuǎn)卡殼。比賽的時(shí)候時(shí)間少，就寫了個(gè)暴力O(n^2)的。

  閱讀全文      摘要: 基本幾何題，判斷線段是否與矩形相交。轉(zhuǎn)化為線段在矩形內(nèi)或線段與四條邊相交。
唯一要注意的是題目中關(guān)于左上角和右下角的定義。

  閱讀全文      摘要: 這個(gè)題需要分情況討論。如果是grid，就能直接算，如果是skew，就一層層往上模擬著堆。最后取最大值。

  閱讀全文      摘要: mmd 和 cz 的智慧結(jié)晶。某次比賽的時(shí)候?qū)懙摹?

  閱讀全文      摘要: 這是胡說八道

  閱讀全文      摘要: 超級(jí)惡心的精度題。注意讀清題意，然后直接做就行了。

  閱讀全文      摘要: 給出一個(gè)沒有偶圈的簡單無向圖，求兩個(gè)頂點(diǎn)間路徑的數(shù)目

  閱讀全文      摘要: Pick公式的應(yīng)用。先介紹一下Pick公式：
a = e / 2 + i - 1
a為多邊形（頂點(diǎn)都在格點(diǎn)上）面積，e為多邊形邊上的格點(diǎn)數(shù)，i為多邊形內(nèi)部的格點(diǎn)數(shù)。
題目給出三點(diǎn)坐標(biāo)，邊上的格點(diǎn)數(shù)可用gcd求得，剩下的事就是解方程了。

  閱讀全文      摘要: 喜歡搞笑的詩的請(qǐng)進(jìn)

  閱讀全文      摘要: 枚舉三角形，然后判斷是否其余的點(diǎn)都不在形內(nèi)，也不在邊上。時(shí)間復(fù)雜度是O(n^4)。

  閱讀全文