F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 4152. -- [AMPPZ2014]The Captain

4152: [AMPPZ2014]The Captain

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 2204  Solved: 873
[Submit][Status][Discuss]

Description

给定平面上的n个点,定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|),求从1号点走到n号点的最小费用。

Input

第一行包含一个正整数n(2<=n<=200000),表示点数。
接下来n行,每行包含两个整数x[i],y[i](0<=x[i],y[i]<=10^9),依次表示每个点的坐标。

Output

一个整数,即最小费用。

Sample Input

5
2 2
1 1
4 5
7 1
6 7

Sample Output

2

HINT

Source

鸣谢Claris上传

[Submit][Status][Discuss]

HOME Back