Statistics

Problem Statement for "Airways"

Problem Statement

Air traffic control requires that the routes of aircraft be restricted. We want to investigate the costs of requiring aircraft to fly only in a few directions. For example, we could require them to fly only north, east, south, or west.

It makes sense to distribute the allowable directions evenly. If we allow only n directions, one will be east and the others will be evenly distributed among all other possible directions. So if n is 3, the three directions are east, 30 degrees west of north, and 30 degrees west of south. Adjacent directions then differ by 120 degrees. Notice that if a direction is legal the opposite direction may not necessarily be legal.

The following picture shows a minimum way to fly to a destination which is 5 east and 3 north of the starting point when n is 8. The 8 allowable directions are shown in blue. By flying a distance of 3*sqrt(2) northeast, and then 2 east (or 2 east, and then 3*sqrt(2) northeast) we can get to our destination by travelling a total distance of 3*sqrt(2) + 2. Notice that for any n and destination the minimal distance can be achieved using no more than two directions.

Create a class Airways that contains a method distance that is given n (the number of legal directions), east (the distance eastward to our destination), and north (the distance northward to our destination). It returns the minimum distance we will have to fly to get to our destination under these requirements.

Definition

Class:
Airways
Method:
distance
Parameters:
int, int, int
Returns:
double
Method signature:
double distance(int n, int east, int north)
(be sure your method is public)

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

  • n will be between 3 and 40, inclusive.
  • east and north will be between -5000 and 5000, inclusive.

Examples

  1. 3

    -219

    0

    Returns: 437.99999999999994

    We want to go 219 due west. One way to do that is to fly 219 in the direction that is 30 degrees west of due south, then fly 219 in the direction 30 degrees west of due north. Our path will form 2 sides of an equilateral triangle.

  2. 3

    171

    0

    Returns: 171.0

    We want to go due east, and that is always an allowed direction.

  3. 4

    233

    3111

    Returns: 3344.0000000000005

    We can go 3111 due north and then 233 east since these are legal directions when n is 4.

  4. 40

    -2912

    -487

    Returns: 2954.3363333516754

  5. 40

    -66

    -66

    Returns: 93.3380951166242

  6. 37

    2000

    0

    Returns: 1999.9999999999989

  7. 7

    4000

    0

    Returns: 3999.999999999999

  8. 3

    -12

    8

    Returns: 24.000000000000004

  9. 3

    12

    -8

    Returns: 25.856406460551014

  10. 5

    0

    -2

    Returns: 2.3511410091698925

  11. 17

    0

    0

    Returns: 0.0

  12. 6

    6

    -6

    Returns: 9.464101615137753

  13. 35

    4000

    -3933

    Returns: 5629.6661763113625

  14. 12

    -6

    0

    Returns: 5.999999999999999

  15. 40

    -2345

    -675

    Returns: 2445.3211930888883

  16. 8

    -97

    97

    Returns: 137.17871555019022

  17. 8

    23

    23

    Returns: 32.526911934581186

  18. 8

    92

    92

    Returns: 130.10764773832474

  19. 16

    46

    46

    Returns: 65.05382386916234

  20. 16

    51

    51

    Returns: 72.12489168102783

  21. 16

    50

    50

    Returns: 70.71067811865474

  22. 24

    -92

    92

    Returns: 130.1076477383247

  23. 24

    92

    -92

    Returns: 130.1076477383247

  24. 24

    -23

    23

    Returns: 32.52691193458117

  25. 32

    46

    46

    Returns: 65.05382386916233

  26. 3

    1792

    -1396

    Returns: 4209.942927366151

  27. 13

    3862

    1002

    Returns: 4108.970818758039

  28. 19

    -2085

    1725

    Returns: 2742.275961303382

  29. 26

    2803

    -4876

    Returns: 5661.380470110123

  30. 29

    4215

    3346

    Returns: 5392.725777341106

  31. 33

    -1497

    397

    Returns: 1552.1080693262031

  32. 16

    885

    -738

    Returns: 1168.310191589662

  33. 32

    1946

    4602

    Returns: 5000.016152813741

  34. 14

    -3840

    -1768

    Returns: 4243.534462721784

  35. 40

    -3508

    4904

    Returns: 6032.869654793278

  36. 16

    -1448

    -963

    Returns: 1773.050807101238

  37. 38

    -1286

    2460

    Returns: 2785.0862570014574

  38. 29

    -1028

    -3168

    Returns: 3347.166743168894

  39. 20

    -4196

    4377

    Returns: 6137.590357156143

  40. 21

    -4031

    -2268

    Returns: 4660.229301859284

  41. 4

    233

    3111

    Returns: 3344.0000000000005

  42. 3

    171

    0

    Returns: 171.0

  43. 14

    -3840

    -1768

    Returns: 4243.534462721784

  44. 39

    13

    15

    Returns: 19.90541142587058

  45. 3

    -5000

    -5000

    Returns: 9999.999999999996

  46. 4

    -5000

    5000

    Returns: 9999.999999999998

  47. 40

    -5000

    2100

    Returns: 5439.8019645376635

  48. 4

    0

    0

    Returns: 0.0

  49. 37

    0

    -3700

    Returns: 3710.0316063266996

  50. 3

    -219

    0

    Returns: 437.99999999999994

  51. 38

    -2005

    -3059

    Returns: 3657.9711331731023

  52. 40

    0

    1000

    Returns: 999.9999999999993

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: