1884: 派送路线

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

FJ有 N 个农场,每个农场具有独立的整数坐标 (x_i, y_i) 。
他需要一个物资配送路线,从第1个农场出发,依次经过农场1,农场2,农场3…,最后从农场N回到农场1。
FJ每次只能朝东南西北四个方向行走,每行走一个单位长度需要1分钟。
除了农场1,其他农场能且仅能到达一次。
请计算FJ的最小时间花费。

输入格式

输入第一行为正整数 N 。(1 <= N <= 100)
接下来 N 行,每行两个正整数 x_i,y_i 。(1 <= x_i, y_i <= 1,000,000)

输出格式

输出一个数字表示答案。
如果不存在配送路线,输出-1。

输入样例 复制

4
2 2
2 4
2 1
1 3

输出样例 复制

12

数据范围与提示

FJ可以在12分钟内完成他的送货路线:
从农场1到农场2:2分钟
从农场2到农场3:规避农场1,5分钟
从农场3到农场4:3分钟
从农场4到农场1:2分钟
来源:USACO 2012.1