首先强调下  就是点集中（n>=2)的最远点对一定是其凸包点集形成的凸多边形的两个顶点 （若所有点在一条直线上就是形成线段的端点）
然后本题求完凸包后可以采用枚举的方法 这种方法就不说了 只要你的凸包点集包含了所有的顶点

关于求得的凸包点集  可以只求出顶点 也可以求出所有在凸多边形上的点
于是在这儿就产生了不同  若凸包点集包含所有在凸多边形上的点的话 我的RC是会处理错误的
若只包含顶点集 我的RC是正确的
所以我想的话 用RC来求点集的最远点对  求得的凸包点集是不能包含非顶点的
所以用RC来做这个题的话  凸包求后凸包点集只能包含顶点
于是我们可以用极角序凸包 或者 水平序凸包 来求凸包点集
因为不包含非顶点  所有在弹栈的时候取严格去点  将在所有非顶点的点去掉
用水平序凸包可以很好的去掉这些点 
似乎用极角序凸包也可以很好的去掉这些点  但是不然~
（lrj的书上是说的极角序凸包得到这些非顶点会有bug，不过如果你的程序中用的初始栈大小为3的话，去掉这些点也是会有bug的）
比如下面这个点集
8  
0 0
1 0
2 0
2 1
2 2
1 2
0 2 
0 1
有些极角序凸包严格筛点后得到的点集是    // 初始栈大小为3的话 此时包含的三个点是一条直线上的  后面又无法去掉那个中间点
0 0
1 0   //  这个点是不能要的
2 0
2 2
0 2
水平序严格筛点后得到的点集是
0 0
2 0
2 2
0 2
这题我测了多次 就是因为我的极角序凸包后的RC一直不能AC  原来是因为我所认为的去掉了非顶点的极角序凸包却包含了非顶点  然后RC处理不了
将极角序凸包初始栈大小设为2的话就可以很好的去掉所以非顶点了
。。。。。
还好  试了这么多次 终于用水平序凸包  还有 极角序凸包  之后的RC  过了这个题
对这两种求凸包的方法及RC也还有些许体会   贴上这些体会 希望有点帮助吧
另外希望得到验证  RC可以处理包含非顶点的凸包点集吗？（我写的RC通过这题验证是不能处理的）

• 我来说三点 (160) 3xian 2009-09-04 17:06:26
  • 关于这三点~ (448) alpc56 2009-09-08 13:07:09