Problem Statement |
| | In a wireless network, the distance between nodes determines connectivity and latency. The further apart two nodes are the slower the connection. If two nodes are further apart than the maximum allowable range they cannot directly communicate. In our network, there will be 2 kinds of nodes: stationary and roaming. When a roaming node wants to communicate with another roaming node it must first communicate with one of the stationary nodes in its range. The stationary node it connects to will then send the transmission through as many stationary nodes as are necessary before finally sending to the destination roaming node. In other words, the transmission always starts at a roaming node, goes through one or more stationary nodes, and finally arrives at the destination roaming node. For example:
R = roaming, S = stationary
.......--R......
....../.........
.....S--........
........\.......
.........S......
.........|......
..R--.../.......
.....\-S........
Above is one possible route between the two depicted roaming nodes.
In this problem you will be given the initial positions of the roaming nodes and their initial velocities. Each roaming node will either be moving upward, leftward, rightward, or downward at the rate of one square per second. For example:
roamNodes Input Format: Direction X Y
roamNodes = {"UP 9 0","DOWN 2 6"}
statNodes Input Format: X Y
statNodes = {"5 2","9 4","7 7"}
Time 0 Time 1 Time 2
0123456789012345 0123456789012345 0123456789012345
0.......--R...... 0................ 0................
1....../......... 1....../--R...... 1................
2.....S--........ 2.....S.......... 2.....S...R......
3........\....... 3..../........... 3.........|......
4.........S...... 4.../.....S...... 4..R------S......
5.........|...... 5..R............. 5................
6..R--.../....... 6................ 6................
7.....\-S........ 7.......S........ 7.......S........
Above are the positions of the nodes, and some possible routes.
We are going to assume that the routing protocol will always choose the shortest possible end-to-end (roaming node-to-roaming node) route when connecting two roaming nodes. You will be given the wireless range of all nodes, the positions and velocities of the roaming nodes, and the positions of the stationary nodes. You will determine the length of the shortest route that will ever occur between the two roaming nodes in the system at any non-negative integral time. The distance between two nodes is always measured using the cartesian distance formula: sqrt((x2-x1)^2 + (y2-y1)^2). The length of a route is the sum of the distances when travelling from node to node along the route. If two nodes share the same location, their distance is 0. Two nodes (Roaming to Static or Static to Static) can communicate if their distance is less than or equal to the given maximum range. Round final answers to the nearest integer. If the two roaming nodes could never communicate return -1. See examples for further clarification.
Create a class Wireless that contains the method bestRoute, which takes an int range, a String[] roamNodes, and a String[] statNodes and returns an int representing the length of the shortest route between the two roaming nodes in the system at any integral time greater than or equal to 0. If the two nodes could never communicate return -1.
|
| |
Definition |
| | | Class: | Wireless | | Method: | bestRoute | | Parameters: | int, String[], String[] | | Returns: | int | | Method signature: | int bestRoute(int range, String[] roamNodes, String[] statNodes) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Two nodes (Roaming to Static or Static to Static) can communicate if their distance if less than or equal to the given maximum range. |
| - | Final answers must be rounded to the nearest integer (i.e. .5 and greater rounds up, below .5 rounds down) |
| - | All routes must start at a roaming node, pass through 1 or more static nodes, and complete at a roaming node. |
| - | UP means INCREASING Y coordinate whereas DOWN means DECREASING Y coordinate |
| - | RIGHT measn INCREASING X coordinate whereas LEFT means DECREASING X coordinate |
| |
Constraints |
| - | range will be between 1 and 30000 inclusive |
| - | roamNodes will contain exactly 2 elements |
| - | Each element of roamNodes will be of the form: Direction X Y where
Direction is one of UP, DOWN, LEFT, or RIGHT
X is an integer with no leading zeros between -10000 and 10000 inclusive
Y is an integer with no leading zeros between -10000 and 10000 inclusive |
| - | statNodes will contain between 1 and 30 elements inclusive |
| - | Each element of statNodes will be of the form: X Y where
X is an integer with no leading zeros between -10000 and 10000 inclusive
Y is an integer with no leading zeros between -10000 and 10000 inclusive |
| - | The final answer will be within .4999 of the nearest integer. |
| |
Examples |
| 0) | |
| | 1 | {"DOWN 100 200","DOWN 100 200"} | {"1000 1000"} |
| Returns: -1 | | The roaming nodes will never be close enough to the static node to communicate. |
|
|
| 1) | |
| | 30000 | {"DOWN 10000 10000","RIGHT -10000 -10000"} | {"10000 -10000","10000 -10000"} |
| Returns: 0 | | They keep getting closer and closer until finally they all meet at the stationary node at (10000,-10000) |
|
|
| 2) | |
| | 3000 | {"DOWN 0 10000","LEFT 10000 0"} | {"14 100","25 -10","98 204","99 1000"} |
| Returns: 49 | |
|
| 3) | |
| | 30000 | {"DOWN 0 0","DOWN 0 0"} | {"10000 10000","9000 10000","8000 10000","7000 10000"} |
| Returns: 24413 | |
|
| 4) | |
| | 20 | {"DOWN -20 0","DOWN 80 1"} | {"0 0","20 0","40 0","60 1"} |
| Returns: -1 | |
|