| | 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. |
| | {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,
27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49} | {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,
27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49} |
| Returns: 1 | |
|
| | {1593,-88517,14301,3200,6,-15099,3200,5881,-2593,11,57361,-92990} | {99531,-17742,-36499,1582,46,34001,-19234,1883,36001,0,233,485} |
| Returns: 73418 | |
|