UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2053. SRM199 ClosestPoints

统计 下载数据

Description

给出N,Range,Seed_0,按照Seed_{i+1} = (Seed_i * 16807) mod (2^31-1)以及Rand_i = (Seed_i mod (2 * Range)) – Range的规则,计算出Rand_1 到Rand_{3n} 。定义三维空间内的点P_k的坐标为(Rand_{3k-2}, Rand_{3k-1}, Rand_{3k}){1≤k≤n}。求出所有点中两点间最小距离的平方以及有多少对点的距离等于最小距离。 2 ≤ N ≤ 150000,1 ≤ Range ≤ 10^6,1 ≤ Seed ≤ 10^3 
注意:如果有多个点重合,就当成一个点

Input

Output

Sample Input

3
100
1

Sample Output

9163
1

Hint

The three points are: (-93, -51, -27), (-42, 30, -28), and (44, -22, 23). The closest pair of points are the first and third, and the square of their distance is 9163. There is 1 pair of points with a squared distance of 9163.

Source