#P1632. 点的移动

点的移动

题目描述

平面上有 NN 个整数坐标点。如果将点 (x0,y0)(x_0,y_0) 移动到 (x1,y1)(x_1,y_1),则需要的代价为 x0x1+y0y1|x_0-x_1|+|y_0-y_1|。求使得 K(K=1,,N)K(K=1, \cdots ,N) 个点在同一位置上最少需要的代价。

输入格式

第一行一个正整数 NN

接下来 NN 行,每行两个正整数 xix_iyiy_i,为第 ii 个点的坐标,不超过 10610^6

【数据规模】。

对于 100%100\% 的数据中,满足 1N501 \le N \le 50

输出格式

输出共 NN 行,第 ii 行为使得有 ii 个点在统一位置的最少代价。

4
15 14
15 16
14 15 
16 15
0
2
3
4