| 题目名称 | 1790. [USACO Feb07]新牛舍 |
|---|---|
| 输入输出 | newbarn.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 12 |
| 题目来源 |
 cstdio
于2014-11-02加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：17， 提交：32， 通过率：53.13% | ||||
 葳棠殇 |
100 | 0.010 s | 0.75 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.012 s | 0.47 MiB | C++ |
 炎帝 |
100 | 0.012 s | 2.20 MiB | C++ |
 forever |
100 | 0.013 s | 2.01 MiB | C++ |
 /k |
100 | 0.015 s | 0.62 MiB | C++ |
 苏轼 |
100 | 0.016 s | 0.28 MiB | Pascal |
 阿狸 |
100 | 0.016 s | 0.39 MiB | C++ |
 stone |
100 | 0.017 s | 0.39 MiB | C++ |
 zy |
100 | 0.018 s | 0.24 MiB | Pascal |
 夜雨 |
100 | 0.020 s | 0.52 MiB | C++ |
| 关于 新牛舍 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
数据没有问题吧？？
stone
2015-10-25 19:51
3楼
| ||||
|
不严谨......
苏轼
2014-11-04 19:32
2楼
| ||||
|
强行规定不能建在点上真的有意义吗……
 cstdio
2014-11-02 18:23
1楼
| ||||
zys【题目描述】
经过多年的积蓄，农夫约翰决定造一个新的牛舍。他知道所有N(2<=N<=10000)头牛的吃草位置，所以他想把牛舍造在最方便的地方。每一头牛吃草的位置是一个整数点(Xi,Yi)（-10^4<=Xi,Yi<=10^4）。没有两头牛的吃草位置是相邻的。
约翰决定把牛舍造在一个没有牛吃草的整数点上。如果牛舍在(X,Y)，在(Xi,Yi)的牛到牛舍的距离是|X-Xi|+|Y-Yi|。约翰把牛舍造在哪儿才能使所有牛到牛舍的距离和最小。
【输入格式】
第1行：一个数N。
第2到N+1行：第i+1行包含第i头牛的位置(Xi,Yi)。
【输出格式】
两个数，最小距离和及所有可能达到这个距离和的牛舍位置的数目。
【样例输入】
4 1 -3 0 1 -2 1 1 -1
【样例输出】
10 4
【提示】
最小距离和是10，牛舍可以位于(0,-1),(0,0),(1,0),(1,1)。
【来源】
Jeffrey Wang,2007
Translation by Richard Peng