Connection Status:
Competition Arena > BarbarianInvasion2

BarbarianInvasion2

SRM 508 · 2010-11-01 · by gojira_tc

SRM 508 · 2010-11-01 · by gojira_tc · Geometry, Graph Theory, Search
Class Name: BarbarianInvasion2
Return Type: double
Method Name: minimumTime
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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

Submissions are judged against all 146 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BarbarianInvasion2 with a public method double minimumTime(vector<int> boundaryX, vector<int> boundaryY, vector<int> cityX, vector<int> cityY) · 146 test cases · 2 s / 256 MB per case

Submitting as anonymous