摘要: 強烈推薦此題。半平面交算法的一個應用。
具體做法是，把多邊形的每條邊向內平移r單位長度，用這些線段所在直線和原多邊形作半平面交，得到的區域就是半徑為r的圓放入多邊形的可行域。可以證明這個區域一定是凸的，或者退化為一條線段，或一個點。那么，我們就可以在這個區域上求最遠點對啦。
我的做法是O(n^2)的。應該存在O(nlogn)的做法，因為都是凸多邊形，每次半平面交只有最多兩個交點，可二分，而最后的求最遠點對可以旋轉卡殼。比賽的時候時間少，就寫了個暴力O(n^2)的。

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

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

  閱讀全文      摘要: mmd 和 cz 的智慧結晶。某次比賽的時候寫的。

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

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

  閱讀全文      摘要: 給出一個沒有偶圈的簡單無向圖，求兩個頂點間路徑的數目

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

  閱讀全文      摘要: 喜歡搞笑的詩的請進

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

  閱讀全文