主题

主题

 
   

Palace

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5721

Problem Description

The last trial Venus imposes on Psyche is a quest to the underworld. She is to take a box and obtain in it a dose of the beauty of Prosperina, queen of the underworld.

There are n palaces in the underworld, which can be located on a 2-Dimension plane with (x,y) coordinates (where x,y are integers). Psyche would like to find the distance of the closest pair of two palaces. It is the password to enter the main palace.

However, the underworld is mysterious and changes all the time. At different times, exactly one of the n palaces disappears. 

Psyche wonders what the distance of the closest pair of two palaces is after some palace has disappeared.

Print the sum of the distance after every single palace has disappeared. 

To avoid floating point error, define the distance d between palace (x1,y1) and (x2,y2) as d=(x1−x2)^2+(y1−y2)^2.

Input

The first line of the input contains an integer T (1≤T≤5), which denotes the number of testcases.

For each testcase, the first line contains an integers n (3≤n≤10^5), which denotes the number of temples in this testcase.

The following n lines contains n pairs of integers, the i-th pair (x,y) (−10^5≤x,y≤10^5) denotes the position of the i-th palace.

Output

For each testcase, print an integer which denotes the sum of the distance after every single palace has disappeared.

Sample Input

1

3

0 0

1 1

2 2

Sample Output

12


题目大意:

给出平面n个点的坐标(xi,yi)。

依次求出第i(1<=i<=n)个点消失的时候,剩余n-1个点的平面最近点对的距离。

输出所求的n个距离的和。

为了避免精度误差,定义两点之间的距离是(x1-x2)^2+(y1-y2)^2。


个人解法:

开始想了好久……一直不知道如何突破瓶颈。liaoy也是蠢够了……

其实我们发现,如果消失的点不是n个点的最近点对,那么是不会影响到最近点对的距离的……

于是有n-2次消失,最近点对的距离都是n个点的最近点对的距离。剩余2次,也就是n个点的平面最近点对(x,y)消失的时候,重新求一边即可。


代码如下:

https://code.csdn.net/snippets/2310504


补了一下平面最近点对的坑……

 
 
评论