一道有意思的算法题

问题描述：
给定平面上n个点组成的集合X，找出X 中点所张成的周长最大的凸5 边形。
编程任务：
对于给定的平面点集X，设计一个算法，求X 中点张成的周长最大的凸5边形。
 Input
第一行有1 个正整数n (n<=10000)，表示集合X 中有n个点。接下 来的n行中，每行有2 个整数，分别表示点的x坐标和y坐标值。
 Output
程序运行结束时，输出最大凸5边形的周长。输出结果保 留2 位小数，4 舍5入。

此题是算法题，求高效解题方法，如果不能AC的话，不算...

如果求精确解,似乎只能穷举,耗时O(n^5).题目中,n=10000,O(n^5)太慢了.
如果求近似解,可以这样做:
STEP1: 求 x1,x2,...xn 的中位数,令它是 xm.该步耗时 O(n);
STEP2: 求 y1,y2,...,yn的中位数,令它是 ym.该步耗时 O(n);
STEP3: 构造数组 A={<1,R1>,<2,R2>,...,<i,Ri>,...,<n,Rn>},其中,Ri是 (xi,yi)到(xm,ym)的距离.即 Ri=((xi-xm)^2+(yi-ym)^2)^0.5. 该步耗时 O(n);
STEP4: 对 A 按 Ri 排序.该步耗时 O(nlogn);
STEP5: 令排好序的 A'={<c1,Rc1>,<c2,Rc2>,...<cn,Rcn>},其中,Rc1<=Rc2<=...<=Rcn
STEP6: for (k=10;k<=n;k++)
STEP6.1: 在 A' 的最后 k 个元素中,用穷举法寻找周长最长的凸5 边形,
STEP6.2: 如果找到,返回该解,
STEP7: 返回无解.