bzoj#P2675. Bomb

Bomb

题目描述

A 国和 B 国是两个超级大国,长期处于冷战状态;A 国在 B 国中设有 NN 个情报站,编号为 1,2,3,,N1,2,3,\dots,N,每个情报站有一个坐标 (Xi,Yi)(X_i,Y_i)。但是,A 国的工作人员发现,每个情报站里都被埋上了炸弹!这些炸弹非常特殊,只要同时拆除其中的三个炸弹,所有炸弹就都不会爆炸了。由于各个情报站联络需要代价,拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。

现在 A 国的指挥部门找到了你,希望知道可能需要的最大代价和最小代价。

输入格式

输入的第一行包含一个整数 NN。接下来 NN 行,第 i+1i+1 行两个整数 Xi,YiX_i,Y_i,表示第 ii 个情报站的坐标。

输出格式

输出两行,每行包含一个整数,第一行表示可能的最大代价,第二行表示可能的最小代价。

样例输入

4
1 1
1 2
2 1
2 3

样例输出

6
4

数据规模与约定

对于 30%30\% 的数据,N<500N<\le 500

对于另外 10%10\% 的数据,每个点出现至少两遍。

对于 50%50\% 的数据,N103N\le 10^3

对于 60%60\% 的数据,N<=8×103N<=8\times 10^3

对于 70%70\% 的数据,N<=1.5×104N<=1.5\times 10^4

对于 80%80\% 的数据,N<=5×104N<=5\times 10^4

对于 100%100\% 的数据,N<=1050Xi,Yi<=108N<=10^5,0\le X_i,Y_i<=10^8

提示

对于两个点 (X0,Y0),(X1,Y1)(X_0,Y_0),(X_1,Y_1),它们之间的曼哈顿距离为 abs(X0X1)+abs(Y0Y1)abs(X_0-X_1)+abs(Y_0-Y_1)。其中 abs(x)abs(x) 表示 xx 的绝对值。