Problem hidden
ACM_0118 - 3 NEAREST VILLAGES
Assume the locations of any three villages are (x1, y1, z1), (x2, y2, z2) and (x3, y3, z3). The distance of the paths passing through any three villages are defined as
D = d_{12} + d_{23}, where d_{ij} = |x_{i} - x_{j}| + |y_{i} - y_{j}| + |z_{i} - z_{j}|.
Determine the shortest path passing through the three closest villages.
Input
The first line specifies the number of villages, N (where 3 <= N <= 10,000). Each of the following N lines specifies the location (x, y, z) of each village (where -1000 <= x, y, z <= 1000).
Output
One line specifies the length of the shortest path passing through the three closest villages.
Examples
№ |
stdin |
stdout |
1 |
9 0 0 1 0 0 2 0 0 3 0 0 4 0 0 6 0 0 8 0 0 7 0 0 9 0 0 10 |
2 |
Added by: | Հրանտ Հովհաննիսյան |
Date: | 2014-02-02 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Thailand Central Group A 2013.B |