城市中心

题目描述

大城市的道路是相互平行或垂直的，如果在城市的道路上行走，不能用点与点之间的直线距离计算长度，而是应该定义两个点（设坐标分别为 $(x,y)$ 与 $(x',y')$）的城市距离为

给定 $n$ 个点的坐标，请在二维平面中找到一个聚会中心点，使得给定点到这个中心的城市距离之和最小，输出这个最小值。

输入格式

第一行：单个整数 $n$。 第二行到第 $n+1$ 行：第 $i+1$ 行有两个整数 $x_i$ 和 $y_i$，表示一个点的坐标。

输出格式

单个整数：表示各点到中心的距离之和的最小值。

数据范围

$-5000 \le x_i, y_i \le 5000$； 对于 30% 的数据，$1 \le n \le 20$； 对于 60% 的数据，$1 \le n \le 2000$； 对于 100% 的数据，$1 \le n \le 100000$。

样例输入

4
1 0
0 1
-1 0
0 -1

样例输出

4

说明：最优中心应该设置在 (0,0) 处。

知识点与难度

本题涉及的知识点从属于 GESP五级（中位数、贪心），难度等级：⭐⭐⭐。

测试点分布