请教一道面试算法题~

羡慕会n^2的大佬，我只会O(n^3logn)

目测次梯度优化

二维难道不是两个中位数的组合吗？反正x y是互相不影响

    应该是曼哈顿距离吧。          将点按x升序排序，则第k个的点到其它点的x总距离=(k-1)x-sum(1~k-1)  +  sum(k+1~n)-(n-k)x， 其中sum( i ~ j )为i到j点的x总和（可以用O(1)的复杂度求出）。     然后将点按y升序排序，以类似方法求得每个点到其他点y的总距离。     最后从n个点里挑出x，y总距离最小的。     总时间复杂度为排序的时间复杂度O(nlogn)

先按x的大小排序，然后通过几何判断出和最大的点只能是第一个点或者最后一个点，比较一下这两个点的距离和，找出和最大的点？