Problem Statement |
| | You are given a two dimensional map. The lower left corner is at the coordinates (0, 0), and the upper right corner is at the coordinates (xSize, ySize).
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.
|
| |
Definition |
| | | Class: | CirclesOfDestruction | | Method: | exitTime | | Parameters: | int, int, int, int, int[], int[] | | Returns: | double | | Method signature: | double exitTime(int xSize, int ySize, int px, int py, int[] x, int[] y) | | (be sure your method is public) |
|
| |
|
| |
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. |
| |
Examples |
| 0) | |
| | | Returns: 5.0 | | The best escape route is a straight line from (5, 5) to (10, 5).
|
|
|
| 1) | |
| | 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. |
|
|
| 2) | |
| | 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. |
|
|
| 3) | |
| | | 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). |
|
|
| 4) | |
| | 100 | 100 | 50 | 50 | {10, 30, 70, 90, 10, 30, 70, 90} | {90, 70, 30, 10, 10, 30, 70, 90} |
| Returns: -1.0 | |
|
| 5) | |
| | 1000 | 1000 | 800 | 800 | {1000, 800, 600} | {800, 1000, 750} |
| Returns: 805.4744331758768 | |
|