Connection Status:
Competition Arena > Flee

Flee

SRM 662 · 2015-06-30 · by cgy4ever

SRM 662 · 2015-06-30 · by cgy4ever · Geometry
Class Name: Flee
Return Type: double
Method Name: maximalSafetyLevel
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You are a point in the plane. You start at the coordinates (0, 0) and you want to flee far away, to the coordinates (10^100, 0). Your path can be any continuous curve.

You are given int[]s x and y. For each valid i, there is a guard standing on the point with coordinates (x[i], y[i]). The guards do not move. You want to avoid the guards as much as possible.

Formally, for any point P in the plane, we define its safety level S(P) as the distance to the closest guard. The safety level of a path is the minimum safety level of a point on the path. Find a path with the largest possible safety level and return its safety level.

Notes

  • Your return value must have an absolute or a relative error smaller than 1e-9.

Constraints

  • x will contain between 1 and 3 elements, inclusive.
  • x and y will contain the same number of elements.
  • Each element in x and y will be between -1,000 and 1,000, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{1,1,-7}
{5,-5,0}
Returns: 5.0

You can go from (0, 0) to (10^100, 0) directly. The safety level of this path is 5, because when you are at (1, 0) the distance to the closest guard is 5.

1)
{1,1}
{-5,-5}
Returns: 5.0990195135927845

One optimal path is the following polyline: (0, 0) -- (-100, 0) -- (-100, -10000) -- (10^100, 0).

2)
{1,1,-8}
{5,-5,0}
Returns: 5.0990195135927845
3)
{232,312,-432}
{498,-374,24}
Returns: 432.6661530556787
4)
{0}
{0}
Returns: 0.0

Each valid path starts in the point (0, 0). This point contains a guard and therefore its safety level is 0. Hence, the safety level of any valid path will be 0.

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

Coding Area

Language: C++17 · define a public class Flee with a public method double maximalSafetyLevel(vector<int> x, vector<int> y) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous