Problem 2156. -- 一道数学题

2156: 一道数学题

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 547  Accepted: 74
[Submit][Status][Web Board]

Description

        如题,这是一道数学题,而且是"2085:HLD的连线游戏"的加强版。
公元2333年的某一天早晨,Taki很早就起床了,准备跟他的好朋友lenka一起出去玩。lenka昨天晚上说她今天早上会来找Taki一起出去玩,但却没说具体什么时候来找他。
        于是倍感无聊的他随手翻开了一本书,他发现书上有n个点,每个点都可以由一个坐标(x,y)表示,他突然想用笔把每2个点都用线段连起来,看最后会是个什么图案。但是如果连线的途中lenka来了,那么Taki立马就会丢下笔跟lenka一起去玩。但如果他把所有线段都连起来了,lenka还是没来的话,他就会主动去找lenka。
        已知每连接2个点(x1,y1),(x2,y2),都要花费时间t=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
        那么Taki在连线上最多可能要花多少时间?

Input

多组输入数据。每组数据第一行1个整数n(2<=n<=1e6)。随后n行每行2个整数(x,y)代表一个点的坐标(-1000<=x,y<=1000)。

Output

每行输出一个整数代表Taki最多的花费时间。

Sample Input

2
1 1
0 0
3
2 2
1 1
0 0

Sample Output

2
12

HINT

 此题要化简一下公式,不能暴力。

Author

dp

[Submit][Status][Web Board]