Problem Statement   A barbarian tribe has surrounded a country. Its border has a shape of a strictly convex polygon (see notes for the exact definition) denoted by points (boundaryX[i], boundaryY[i]) in counterclockwise order. There are N cities strictly inside the country which we shall consider as points (cityX[i], cityY[i]). The barbarians have spread out along the entire perimeter of the border so that the distance between consecutive barbarians (measured along the country perimeter) is always constant. It is known that one of the barbarians stands exactly at point (boundaryX[0], boundaryY[0]). The exact number of barbarians is 1,000,000! = 1 * 2 * ... * 1,000,000. They want to divide into N equal groups such that each group attacks one particular city. There are no restrictions on the groups. In particular, a group doesn't have to contain only barbarians standing next to each other. Knowing that a barbarian walks one unit of distance in one hour, determine the minimum time in hours the last person of the last group will need to reach the cities if they divide and move optimally. Assume that barbarians and cities are points on the plane.   Definition   Class:  BarbarianInvasion2  Method:  minimumTime  Parameters:  int[], int[], int[], int[]  Returns:  double  Method signature:  double minimumTime(int[] boundaryX, int[] boundaryY, int[] cityX, int[] cityY)  (be sure your method is public) 
    Notes    The returned value must have an absolute or relative error less than 1e9.    A polygon is convex if it does not intersect itself, and every straight line joining any two interior points of the polygon is entirely contained in the polygon's interior.    A polygon is strictly convex if it is convex and no three consecutive vertices lie on the same straight line.   Constraints    boundaryX will contain between 3 and 50 elements, inclusive.    boundaryY will contain the same number of elements as boundaryX.    Each element of boundaryX and boundaryY will be between 1000 and 1000, inclusive.    The points (boundaryX[i], boundaryY[i]), taken in order, will describe a counterclockwise traversal of vertices in a strictly convex polygon.    cityX will contain between 1 and 5 elements, inclusive.    cityY will contain the same number of elements as cityX.    Each element of cityX and cityY will be between 1000 and 1000, inclusive.    The points (cityX[i], cityY[i]) will be distinct.    The points (cityX[i], cityY[i]) will lie strictly inside the boundary polygon.   Examples  0)     Returns: 1.414213562373088  There is only one city in the country. So every barbarian will attack this city. The last barbarians to reach this city are on the corners. Each person from the corners needs square_root(2) hours to reach the city. 

 1)     Returns: 2.8284271247461485  This time, the last person is from the corner (3,3), and needs 2*square_root(2) hours to reach the city. 

 2)    {0,3,3,0}  {0,0,3,3}  {1,2}  {2,1} 
 Returns: 2.236067977499772  Now we have 2 cities in the country. Let's divide the barbarians into 2 groups. Group 1 consists of barbarians on borders (0,0)(3,0) and (3,0)(3,3). Group 2 consists of barbarians on borders (3,3)(0,3) and (0,3)(0,0). These 2 groups have an equal number of barbarians. The last person needs square_root(5) hours to reach the city, which is the best solution. 

 3)    {0,40,40,0}  {0,0,40,40}  {1,2,31,2,15}  {1,2,3,3,24} 
 Returns: 38.05748153551994  
 4)    {0,124,6,120,300}  {0,125,140,137,100}  {10,10,10,10}  {50,51,52,21} 
 Returns: 332.77770358002783  

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.
