UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4152. [AMPPZ2014]The Captain

统计 下载数据

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上传

中文 English

Server time: 2024-04-19 14:01:40 | 开源项目