一个街区有很多住户,街区的街道只能为东西,南北两种方向.
用(xy)来表示住户坐在的街区.
例如(420),表示用户在东西方向第4个街道,南北方向第20个街道.
现在要建一个邮局,使得各个住户到邮局的距离之和最少.
求现在这个邮局应该建在那个地方使得所有住户距离之和最小;
第一行一个整数n<20,表示有n组测试数据,下面是n组数据;
每组第一行一个整数m<20表示本组有m个住户,下面的m行每行有两个整数0<100,表示某个用户所在街区的坐标.
m行后是新一组的数据;
每组数据输出到邮局最小的距离和,回车结束;
这题开始没怎么看懂题目,忽略了街道只有南北和东西走向.南北方向和东西方向,可以分开考虑.坐标轴上的从小到大排列的n个点,A1A2A3...An.那么:
1.首先到所有点距离之和最小的点必须在A1到An之间.
2.距离A1和An点之和最小的点,在A1和An之间.
3.距离A2和A(n-1)点之和最小的点,在A2和A(n-1)之间.符合该条件,也符合条件1.
4.依次类推,不断缩小范围,最后就是中位点.
int sum=0;