U362860 【自用】【JMU算法课作业】求中位数、归并排序

${\rm \textcolor{black} 这题是用来测试归并排序的时间效率的。 自用。}$ 某石油公司有n口油井，为方便输送石油，计划修建输油管道。根据设计要求，水平方向有一条主管道，每口油井修一条垂直方向的支线管道通向主管道。请设计一种算法确定主管道的位置，使得所有油井到主管道之间的支线管道长度的总和最小。 )

意思就是：给定一个长度为n的数列$\{ a_1, \, a_2, \,..., \, a_n \} $，找到一个数t，使得s最大，并输出这个s。 s定义为： $$s = \sum_{i=1}^{n} \lvert a_i-t \rvert $$ 那么很显然t取中位数的时候就是答案。 当然啦， t的取值也未必仅限于一个数。 准确来说，满足条件的t的取值范围是一个闭区间。

第一行一个整数n 随后n行， 每行两个整数x,y, 表示这个油井的坐标

一个整数s 表示答案

**时间限制**555ms **空间限制**55mb **数据范围** 1