货仓选址（二维）题解

题意简述

在二维平面上选择一个合适的点，到N个点的曼哈顿距离之和最小。求离之和的最小值、合适的点位置数目。

分析

从一维的货仓选址得到启发，合适的点应该是位置上的中位数，那么二维也是一样，把x坐标y坐标都排序，再分奇偶讨论，如果是奇数，这样的点（分析至此）就只有一个；如果是偶数，这样的点就是n/2和n/2+1之间横竖线条的交点个数（分析至此）。

悲伤

说“分析至此”的原因是还需要考虑到 “任意两家商店均不在同一位置，也不相邻（距离为 1 即相邻）”。需要特殊处理这些特殊的情况。。。

警示liuyundi以后要认真审题。。。