CirclesOfDestruction
SRM 293 · 2006-03-17 · by supernova
Problem Statement
You start at the coordinates (px, py) and your goal is to reach one of the four edges of the map. You are represented as one point in the plane (infinitely small) and you can move at the speed of one unit of space per one unit of time in any direction of the unit circle.
There are also n points on the map that expand at that same speed (one unit of space per one unit of time) in all directions. That is, after t units of time, there will be n circles, each with a radius of t. The coordinates of these n points are given in the int[]s x and y, where (x[i], y[i]) are the coordinates of the i-th point.
Your task is to determine the minimum amount of time required to reach an edge without stepping inside any of the circles (you can step on the boundary). Output -1 if there is no way to escape.
Notes
- Circles expand independently from each other. They can overlap without causing any interference.
- Your return value must have an absolute or relative error less than 1e-9.
Constraints
- xSize will be between 1 and 1000, inclusive.
- ySize will be between 1 and 1000, inclusive.
- px will be between 0 and xSize, inclusive.
- py will be between 0 and ySize, inclusive.
- x will have between 1 and 50 elements, inclusive.
- Each element of x will be between 0 and xSize, inclusive.
- x and y will have the same number of elements.
- Each element of y will be between 0 and ySize, inclusive.
- Every circle has its own different starting point, which is also different from your own starting point.
- If one can escape at point A at boundary, then there exists an interval of length at least 1e-6, which contains A and escape is possible at any point of this interval.
10
10
5
5
{1, 5, 5}
{5, 1, 9}
Returns: 5.0
The best escape route is a straight line from (5, 5) to (10, 5).
101
10
5
5
{1, 5, 5, 9}
{5, 1, 9, 5}
Returns: -1.0
You cannot reach an edge without stepping inside any of the circles.
4
3
0
2
{0, 0, 1, 1, 1}
{1, 3, 1, 2, 3}
Returns: 0.0
You are already on the edge of the map.
5
6
4
2
{0, 4, 5}
{6, 0, 2}
Returns: 4.0
You can go straight to the point (0, 2). Note that at the moment of your escape, you'll be on the boundary of the circle that started from (0, 6).
100
100
50
50
{10, 30, 70, 90, 10, 30, 70, 90}
{90, 70, 30, 10, 10, 30, 70, 90}
Returns: -1.0
916
792
663
283
{833, 17, 390, 711}
{205, 431, 546, 610}
Returns: 284.28060264123246
916 792 663 283 {833, 17, 390, 711} {205, 431, 546, 610}
94
47
50
16
{31, 65, 58}
{9, 30, 6}
Returns: 34.39491241448363
94 47 50 16 {31, 65, 58} {9, 30, 6}
50
47
25
15
{32, 14}
{6, 39}
Returns: 18.027756377319946
50 47 25 15 {32, 14} {6, 39}
67
100
30
48
{30, 8, 58, 66}
{98, 60, 3, 59}
Returns: 41.6096276252397
67 100 30 48
Submissions are judged against all 70 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CirclesOfDestruction with a public method double exitTime(int xSize, int ySize, int px, int py, vector<int> x, vector<int> y) · 70 test cases · 2 s / 256 MB per case