The Cube

You are locked in “The Cube”. It is a gigantic three-dimensional
structure made up of cubic rooms distributed in a three-dimensional
grid. Therefore, we can identify each room with its coordinates
(x, y, z) ∈ ℤ³. Two rooms that completely share a face are connected.
Hence, every room has six adjacents rooms. You need one minute to move
from a room to any adjacent room.

0.5 After some exploration, you have discovered a way out. You have
identified n special rooms with coordinates (x_(i), y_(i), z_(i)). You
know that at a certain moment an alarm will sound and an announcement of
which of the n rooms is the exit will be broadcast. To maximize your
chances of survival, you will wait in a room that minimizes the average
time to reach a special room.

Can you compute the sum of times to reach every special room if you
place yourself in an optimal room?

0.5

[image]

Input

Input consists of several cases, each with n, followed by n different
triplets x_(i) y_(i) z_(i). Assume 1 ≤ n ≤ 10⁵ and that the coordinates
are natural numbers between 1 and 10⁹.

Output

For every case, print the minimum sum of times to reach every special
room.

Problem information

Author: Edgar Moreno

Generation: 2026-01-25T11:29:18.659Z

© Jutge.org, 2006–2026.
https://jutge.org
