100 300
0    0
120 580
-300 800
-600 -700
500 200
100 -1000
1000 250
01500 2800
2000 2000
210 -1000
-1000 800
300 600
2000 4000
1000 -600
0-6000 1000
-3000 3000
-1500 2000
-1500 -1500
-2000 -500
200 6000
500 8000
5000 7000
-5000 2000
-4000 3000
-6000 6000
9000 9000
-9000 9000
6500 -5000
3500 2000

啥意思，你自己测知道结果就行了呗

不明白为什么不给发......

你直接说结论是中位数不就结了……我从来懒得看证明的……

中位数只是一个答案而已....
x取中间两个数之间的任何值都行...

这个不用证也知道，偶数不影响结果

额. 那不好意思.. 高中生表示不知道您这里说的"偶数"是什么


对偶数情形给一个相当麻烦的证法吧...
该问题是寻找一点要求该点到其他各个点的Eucilid范数之和是最小的, 这里我就不用绝对值运算了(R1中Eucilid范数与绝对值等价), 而采用Eucilid范数的定义
dist = \sum sqrt( (x - x_i) )
问题就是求dist的最小值. 我们通过求dist对x的偏导数取零点即可拿到dist的一个极小值.
d dist = \sum (x - xi)/sqrt((x-x_i)^2)
注意结果中的每一项, 当x > ai时取1, x < ai取 -1, 那么只要i为偶数, 我们让ai均匀地分布于x的两侧即可使d dist == 0, 从而使总距离最短.


严格地说还要验证我们取得的极值是最小值, 考虑到拿到的极值只有一个, 并且距离没有上界,所以断言该极值是最小值.

大帝！！

看不懂。。你是来证明是中值的吧

不是, 我是证明i为偶数时取极值的点构成一个区间.

我有一维复杂度为n的算法。

说说看。

你们都在说神马
36L 44L的简单证法你们认为是怎么样的...

我刚才对奇数情况作了一下讨论, 用的扰动法. 证明了奇数情况下取最小值的点构成横跨两个区段的区间.
因此严格地说36L, 44L的证明有问题.

高中生路过表示不知道您在说神马 ... 是不是在说 你用高级方法 验证了一下 发现我的证明有问题?
那么问题出在哪呢 我高中生可是完全看不出有什么问题啊..

不严密而已. 没关系, 不必深究.
另外说一下O(n)的算法.
其实标准库中已经为你写好了: std::nth_element. 该算法对容器进行排序, 第n个元素到位后直接终止. 平均表现是线性于[first, end).

看错了。。是求学校的位置啊。。我以为学校位置已知 要求别的呢。。。
直接把所有横坐标相加，再除以n得出的值为横坐标
纵坐标同理。就可以了