There are various cities at points around the x-y plane that are separated by great geographical distances, and thus are hard to travel between. The mayors of the cities have decided that they will undertake a road-paving plan to connect all of the cities. However, they do not know how long this will take.
At time zero, the roads are of zero length. Each time unit, the roads leading out of each city in the four cardinal directions (north, east, south, and west) will be extended by one unit. When roads from two different cities both contain at least one point in common, their two cities are connected, and all cities connected to those two cities are also considered connected. Your job is to figure out how long the construction job will take.
You will be given a int x and a int y, where the location of the i-th city is at (x[i], y[i]). Given the locations of all the cities in the x-y plane, your method should return the first time unit at which all the cities are connected to each other.
|Method signature:||int timeTaken(int x, int y)|
|(be sure your method is public)|
|-||Connectedness is transitive; i.e., if city A is connected to city B, and B is connected to C, then A is connected to C.|
|-||x will contain between 1 and 50 elements, inclusive.|
|-||y will contain the same number of elements as x.|
|-||Each element of x will be between -1000000 and 1000000, inclusive.|
|-||Each element of y will be between -1000000 and 1000000, inclusive.|
|-||No two cities will be at the same coordinates.|
|The road north from (0,0) will intersect the road west from (5,5) at t = 5.|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.