4128:通信问题

时间限制:5 S   /  内存限制:65536 KB
AC:12   /  Submit:149
问题描述

某市通信部准备在城市里建造 n 个信号塔,由于信号塔之间也需要通信,因此每建好一个信号塔,他们都需要记录一下当前信号塔与已经建好的所有信号塔中最远的距离。

我们可以粗略的把城市看成一个二维平面,两个信号塔的距离按照曼哈顿距离来算。

曼哈顿距离指:两点在南北方向上的距离加上在东西方向上的距离,即两点的横纵坐标之差的和。

输入描述

第一行是一个正整数 n 表示信号塔的数量。(2 ≤ n ≤ 105

接下来 n 行,每行两个绝对值不超过 109 的整数 x 和 y 表示当前信号塔的横纵坐标。

输入的顺序即为建造信号塔的顺序。

输出描述

从第二个信号塔开始,每建好一个信号塔,输出当前信号塔与已经建好的所有信号塔中最远的距离,然后换行。

最后总共应该输出 n - 1 行。

样例输入复制样例

3

0 0

3 3

-1 -1

样例输出

6

8

提示说明

建议使用更快的输入输出方式。

题目魔改:JMU第八届天梯校选

相关

TKK-ICPC Round#17


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1