/ Vijos / 题库 /

新牛舍

新牛舍

时间限制:1秒  内存限制:256M


【问题描述】

  经过多年的积蓄,农夫JOHN决定造一个新的牛舍。他知道所有 \(N\) 头牛的吃草位置,所以他想把牛舍造在最方便的地方。 每一头牛吃草的位置是一个整数点 \((X_i, Y_i)\)。 没有两头牛的吃草位置是相同的。

  JOHN决定把牛舍造在一个没有牛吃草的整数点上。如果牛舍在 \((X, Y)\),在 \((X_i, Y_i)\) 的牛到牛舍的距离是 \(|X-X_i|+|Y-Y_i|\)。

  JOHN把牛舍造在哪儿才能使所有牛到牛舍的距离和最低?

【输入格式】

  第 1 行: 一个数 \(N\)
  第 \(2~N+1\) 行:第 \(i+1\) 行 包含第i头牛的位置 \((X_i, Y_i)\)。

【输出格式】

  第 1 行: 两个数,最小距离和和所有可能达到这个距离和的牛舍位置的数目。

【输入输出样例】

 Input

4
1 -3
0 1
-2 1
1 -1

 Output

10 4

【样例说明】

  最小距离和是10,可以在牛舍位于 (0, -1), (0, 0), (1, 0), (1, 1)时达到。

【数据说明】

  对于 \(100\%\) 的数据 \(1≤N≤10000\),\(-10000≤X_i,Y_i≤10000\)。

【来源】

  Mr.he

信息

ID
2306
难度
(无)
分类
搜索 | 枚举贪心 | 其他 | 二分查找 点击显示
标签
递交数
0
已通过
0
通过率
?
被复制
4
上传者