摘要: 强烈推荐此题。半平面交算法的一个应用。
具体做法是，把多边形的每条边向内平移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)。

  阅读全文