JOIN
Get Time

   Problem Statement  

 Problem Statement for BarbarianInvasion2

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 counter-clockwise 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 1e-9.
-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)
    
{0,2,2,0}
{0,0,2,2}
{1}
{1}
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)
    
{0,3,3,0}
{0,0,3,3}
{1}
{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.

This problem was used for:
       Single Round Match 508 Round 1 - Division I, Level Three