由于时间所限，剩下的几个问题估计没时间了，在此记一笔：
1、所有立体几何相关的；
2、三角剖分系列；
3、Voronoi 图问题。
等等，还有其它的，想到了再记录，这些题目大致包括：POJ 1379、POJ 3391、POJ 2986、POJ 3675。
参考：http://gccfeli.cn/2008/02/delaunay-triangulation.html
http://blog.csdn.net/donkeylong/archive/2009/12/02/4909774.aspx
gcfeli.cn
http://blog.sina.com.cn/s/blog_5c95cb070100f33y.html
只有因子 2,3,5,7 的数称为丑数，现在要寻找第 k 个丑数。貌似很多这样的题目。
一个序列，112123123412345123456，如此下去，问第 n 位是多少？
基本的数学问题。
http://www.cai0715.cn/oiblog/read.php?286
http://zeming89.blog.163.com/blog/static/5739380420099199429105/?fromdm&fromSearch&isFromSearchEngine=yes
这个题目要求的是多边形的内切圆，内切圆是圆心到各边距离最小值的最大值，对于三角形可以直接套用公式。但是多边形则不可以。
将一个球在多边形内部滚动，逐步增大球的半径，直到无法继续增大为止。这实际就是将多边形的各条边往内部移动。。。移动距离可以采用二分法来确定。
下面还有个直接枚举3条边的办法。
http://hi.baidu.com/greatadam/blog/item/a4570938bf702920b8998fc1.html
参考：
http://gccfeli.cn/2008/09/pku3525.html
http://blog.csdn.net/thszhong/archive/2008/10/03/3014532.aspx
http://imlazy.ycool.com/post.2124481.html
http://hi.baidu.com/superlong/blog/item/becac35cd66e4649faf2c025.html
http://hi.baidu.com/pojoflcc/blog/item/9f8afe264888ad09918f9d99.html
要求找到 N 个点由 3 个点组成的三角形中面积最大的。
肯定是先用凸包来，但是再完成凸包之后枚举时，不需要来个直接的 3 层循环枚举。有些情况是可以砍掉的。
固定前两点 i 和 j，然后顺着凸包枚举下一个点，求面积，可以发现面积是单峰性的。所以如果当前面积小于上面积，就直接 break；
考虑还可以发现，当固定第一个点 i，枚举第二个点 j，依然存在单峰性，如果上次枚举 j 时取得的最大三角形面积对应的第三个点是 k，那么这次下一个 j 时就可以直接从 k + 1 开始，因此第二个循环里面也一样可以加上一个 break。
Read the rest of this entry »
求多边形的一个点，使得它到各个顶点的距离最小。
这一点被称为是费马点，对于三角形，可以有固定的结论，但是对于一般多边形则没有。
Read the rest of this entry »
http://hi.baidu.com/zyylhappy/blog/item/4ec2410b67e07f2f6a60fb0b.html
为了求出多边形相交的面积，需要先求出相交多边形的顶点。
Read the rest of this entry »
求 house 在 property line 上的最大可见区域，中间有各种障碍物。
Read the rest of this entry »
线段树的典型应用。
求 N 个矩形所形成区域的面积。
将输入的坐标离散化。
http://blog.csdn.net/lvlu911/archive/2010/07/10/5725553.aspx
给你一个多边形的N个顶点坐标，然后再给一个钉子，给定钉子的半径和圆心坐标，首先判断多边形是否为凸多边形，若为凸多边形，再判断钉子是否可以放到凸多边形内部。
1.判断是否为凸边变形，第一步将顶点逆时针排列，再根据 pipj 应在pi-1pi 的逆时针方向，若存在 pipj 在pi-1pj 的顺时针方向，则该多边形为凹多边形。
2.判断圆(钉子)是否在多边形内部，第一步判断圆心是否在凸多边形内部，第二步再判断圆心到某一边的最短距离，若存在某最短距离大于圆心，则圆不能放在凸多边内。
Read the rest of this entry »
基本的 DFS 问题。
给定平面上一组点，问可以构成多少个正方形。。
枚举两个点，判断构成正方形的另外两个点是否存在于点中。查找可以使用 hash。。。
不要枚举四个点来判断是否可以构成正方形。
两条线段相交，问最多可以接住多少雨水。貌似不复杂，不过得想清楚哪些情况下是肯定接不住的：线段不相交，线段重合，一条平行于 X 轴等等多种情况。
给定一个三角形，告知其边长，现有一段绳索要放置在三角形中，要使得绳索在三角形中围成的多边形面积尽可能大。问最大面积是多少。
一共有 3 种情况：如果绳索长度超过外围三角形的总长，则最大面积就是三角形的面积；
如果绳索可以在三角形内完全舒展成一个圆，那么总面积就是那个三角形的面积；
第三种情况很复杂，我暂时还没弄清楚。
对于一个三角形，其内切圆的半径是面积的 2 倍除以总周长。
http://hi.baidu.com/goldengoatish/blog/item/969fafdebc862f1a4954031e.html
http://hi.baidu.com/hobbyhcb/blog/item/17201bcb1d40f54ef31fe70d.html
平面上有 N 个点，要求一个矩形，使得它覆盖不少于 M 个点，求这样一个矩形的最小面积，所有的坐标都是整数。如果一个顶点出现在边界，则不被认为是被覆盖。
首先将所有点的 x 轴坐标取出，按升序排序，去重。 将所有点按照 y 轴坐标升序排序。 每次枚举两个 x 轴的坐标 xi、xj，将 x 坐标在 [xi, xj] 范围内的点的 y 坐标依次存入数组 t 中，这样对于这一次枚举，最小的矩形的面积就为 (xj – xi + 2) * min(t[i+m-1] – t[i] + 2) ，其中0 < = i < t.size && 0 <= i+m-1 < t.size，时间复杂度，O(n*n*n)。