Particle Simulator
Time: 6.0 s Memory: 1024 MB
-
Input
The first line of input contains a single integer $N$ ($1 \leq N$), the number of particles. Each of the following $N$ lines contains three space-separated integers $x_i$, $y_i$ and $z_i$ ($-100 \cdot N^{1/3} \leq x_i,y_i,z_i \leq 100 \cdot N^{1/3}$), the coordinates of the particle $i$ in millimeters. All $x_i$, $y_i$ and $z_i$ are generated uniformly at random. Particles can coincide.
Output
Print one integer, the number of pairs $(i,j)$ ($1 \leq i < j \leq N$) such that the euclidean distance between particle $i$ and $j$ is at most 25 centimeters.
Scoring
Solve as many test groups as possible. Secondarily, minimize the runtime for the slowest testcase in a solved test group.
Test group
Limits
$1$
$N \leq 10^4$
$2$
$N \leq 10^5$
$3$
$N \leq 5*10^5$
Sample Input 1 Sample Output 1 4 150 -116 17 -136 -9 -147 2 30 -5 24 51 -104
5
-
To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.
You must log in to register. - Particle Simulator