bzoj#P2675. Bomb
Bomb
题目描述
A 国和 B 国是两个超级大国,长期处于冷战状态;A 国在 B 国中设有 个情报站,编号为 ,每个情报站有一个坐标 。但是,A 国的工作人员发现,每个情报站里都被埋上了炸弹!这些炸弹非常特殊,只要同时拆除其中的三个炸弹,所有炸弹就都不会爆炸了。由于各个情报站联络需要代价,拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。
现在 A 国的指挥部门找到了你,希望知道可能需要的最大代价和最小代价。
输入格式
输入的第一行包含一个整数 。接下来 行,第 行两个整数 ,表示第 个情报站的坐标。
输出格式
输出两行,每行包含一个整数,第一行表示可能的最大代价,第二行表示可能的最小代价。
样例输入
4
1 1
1 2
2 1
2 3
样例输出
6
4
数据规模与约定
对于 的数据,。
对于另外 的数据,每个点出现至少两遍。
对于 的数据,。
对于 的数据,。
对于 的数据,。
对于 的数据,。
对于 的数据,。
提示
对于两个点 ,它们之间的曼哈顿距离为 。其中 表示 的绝对值。