题意：有 n 条线段，问能否找出一条直线使得所有线段都与这条直线有交点。
思路：枚举 n 条线段的两个不相同的点，作为直线上的点进行判断，通过叉积判断是否与其他的线段相交。
Read the rest of this entry »
有 n 个点，任意取三个点，求这三点组成的三角形的外接圆最大半径。
直接枚举算。
顺便想想外心，内心，垂心，重心，是怎么计算的？
Read the rest of this entry »
求凸包的面积，闭上眼睛，把计算几何的凸包复习一遍。
Read the rest of this entry »
http://blog.sina.com.cn/s/blog_5c95cb070100ero4.html
题意：判断一条线段L是否在矩形内部或者与矩形相交（包括规范相交，非规范相交）。
注意：矩形输入的左上角和右下角端点下标需进行判定。
思路：先判断线段是否在矩形内，如果不是的话，再判定矩形的四条线段与线段L相交。
由于时间所限，剩下的几个问题估计没时间了，在此记一笔：
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
这个题目要求的是多边形的内切圆，内切圆是圆心到各边距离最小值的最大值，对于三角形可以直接套用公式。但是多边形则不可以。
将一个球在多边形内部滚动，逐步增大球的半径，直到无法继续增大为止。这实际就是将多边形的各条边往内部移动。。。移动距离可以采用二分法来确定。
下面还有个直接枚举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
求多边形的一个点，使得它到各个顶点的距离最小。
这一点被称为是费马点，对于三角形，可以有固定的结论，但是对于一般多边形则没有。
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个顶点坐标，然后再给一个钉子，给定钉子的半径和圆心坐标，首先判断多边形是否为凸多边形，若为凸多边形，再判断钉子是否可以放到凸多边形内部。
1.判断是否为凸边变形，第一步将顶点逆时针排列，再根据 pipj 应在pi-1pi 的逆时针方向，若存在 pipj 在pi-1pj 的顺时针方向，则该多边形为凹多边形。
2.判断圆(钉子)是否在多边形内部，第一步判断圆心是否在凸多边形内部，第二步再判断圆心到某一边的最短距离，若存在某最短距离大于圆心，则圆不能放在凸多边内。
Read the rest of this entry »
给定平面上一组点，问可以构成多少个正方形。。
枚举两个点，判断构成正方形的另外两个点是否存在于点中。查找可以使用 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)。
题目给定一个图，以及图中个点的坐标，求最外围的区域，其实就是求图中多边形面积的最大者。
利用叉积来求面积。。