HDU 5721 Palace 求最近点对 + 对答案的贡献


Palace

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

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 $ (x_1, y_1) $ and $ (x_2, y_2) $ as $ d = (x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2 $.

Input

The first line of the input contains an integer $ T $ $ (1 \le T \le 5) $, which denotes the number of testcases.
For each testcase, the first line contains an integers $ n $ $ (3 \le n \le 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 \le x,y \le 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

Hint

If palace $ (0,0) $ disappears,$ d = (1-2) ^ 2 + (1 - 2) ^ 2 = 2 $; If palace $ (1,1) $ disappears,$ d = (0-2) ^ 2 + (0 - 2) ^ 2 = 8 $; If palace $ (2,2) $ disappears,$ d = (0-1) ^ 2 + (0-1) ^ 2 = 2 $; Thus the answer is $ 2 + 8 + 2 = 12 $。

Source

 

题意

给出n个点的坐标,假设第i个点消失后,最近点对的距离的平方为d,求d的和。

思路

会发现,这n个点的最近点对的距离对答案的贡献系数为(n-2),因为除了删除这两个最近点对,其它点的删除都不会影响最近点对的距离。后面分别删除这两个点,再求出最近点对的距离求和即可。求最近点对可以用KD-tree或者CDQ分治。
 
KD-tree

 

CDQ分治

 

 

 
 

发表评论

电子邮件地址不会被公开。 必填项已用*标注