Problem D
Space Mail
You are a space postal carrier. Your job is to deliver parcels in your spaceship to every planet in your postal district. The number of parcels you can deliver depends on how much fuel you need to carry in your ship in order to jump from planet to planet while on your delivery route. The less fuel you need to carry, the smaller your fuel tank can be, leaving room for more parcels and ultimately making you richer. Note that you can fill up your tank before each planet-to-planet jump if you want. And since you work for the United Federation of Planets Postal Service, time and the amount of fuel used are irrelevant. (It does not matter how many jumps you make as long the parcels get delivered.)
Given a star map, you must figure out the smallest possible fuel tank to install in your ship in order for you to deliver to all the planets. The amount of fuel required to make a jump between two planets (in litres of plasma fuel) is numerically equal to the distance between the two planets (in light years). For example, a distance of $2.718$ light years requires $2.718$ litres of fuel. It is important, though, that the size of a fuel tank is always an integer value, so for that particular distance you would need a $3$-litre fuel tank or larger.
Write a program that reads in the locations of all the planets and determines the smallest possible fuel tank you should install in your ship. You can begin your delivery route on any planet, but wherever you begin, you must be able to visit all the planets (possibly revisiting planets along the way).
Input
The first line of input contains an integer, $n$, the number of planets in your postal district ($2 \leq n \leq 5\, 000$). This is followed by $n$ lines, each of which contains three space-separated integers, $x$ $y$ $z$, the cartesian coordinates of one planet ($0 \leq x,y,z \leq 1\, 000$). No two planets share the same coordinates.
Recall that if planet $P$ is at $(x_1,y_1,z_1)$ and planet $Q$ is at $(x_2,y_2,z_2)$, then the distance between $P$ and $Q$ is
\[ \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2} \]Output
Output a single integer, the size of the smallest fuel tank your ship will need.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 0 0 0 0 2 2 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 2 3 4 5 6 7 8 9 12 12 12 |
8 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 0 0 0 0 0 1 0 0 2 0 1 2 0 2 2 0 2 1 0 2 0 |
1 |
