TopCoder Statistics - Problem Statement

Problem Statement

Consider the XY plane. The non-negative part of the X axis is a wall. (In other words, the wall is a ray that starts in the point (0, 0) and goes indefinitely in the positive X direction.
There is a robot in the plane. The robot is a circle of radius r. Initially the center of the robot is at the coordinates (x1, y1). The robot needs to move its center to the point (x2, y2). The robot cannot go through the wall, but it can touch the wall at any point.
Compute and return the minimal distance the robot needs to travel.

Definition

Class:: AroundTheWall
Method:: minDistance
Parameters:: int, int, int, int, int
Returns:: double
Method signature:: double minDistance(int r, int x1, int y1, int x2, int y2)
(be sure your method is public)

Notes

The returned value must have an absolute or relative error less than 1e-9.

Constraints

x1, y1, x2 and y2 will each be between -1000 and 1000, inclusive.
r will be between 1 and 50, inclusive.
Points (x1, y1) and (x2, y2) will be distinct.
Both points (x1, y1) and (x2, y2) will be at distance at least r from the wall.

Examples

1

-1

2

-1

-3

Returns: 5.0

Can go straight vertical and just touch the wall midway
1

2

1

2

-1

Returns: 7.141592653589793

Go horizontal, do 180 degree turn around the wall and go horizontal again
5

2

5

-2

5

Returns: 4.0

Can go straight horizontal and just touch the wall
1

1

2

-2

0

Returns: 3.605551275463989

The robot can move in a straight line between the two points, safely avoiding the wall. It will cover a distance of sqrt(22+32) = sqrt(13).
1

10

-1

10

-2

Returns: 1.0

One endpoint touches the wall, still can go straight
1

3

-1

-3

0

Returns: 6.1682640342003126
6

-5

5

-5

-5

Returns: 10.216906813922824

Two
5

-7

1

5

10

Returns: 15.0

Can go straight diagonally and touch the wall midway
5

-7

-1

1

7

Returns: 11.41897054604164

The wall prevents the robot from moving straight between the two points.
5

1

7

-1

-7

Returns: 17.853981633974485

The robot has to make a 90-degree turn to go around the wall.
50

1000

1000

1000

-1000

Returns: 2908.734892250384

Max answer
50

-1000

-1000

1000

1000

Returns: 2830.1950759106394
50

-1000

-1000

-1000

1000

Returns: 2000.0
1

-1000

-1000

1000

1000

Returns: 2828.4278318530005

Straight diagonal would be 2828.42712, just a bit of deviation for 2828.42783
1

1000

1000

1000

-1000

Returns: 2829.9986281797956
1

1000

2

1000

-2

Returns: 2003.1425926530064
49

-30

-40

-40

-30

Returns: 14.142135623730951
49

-30

-40

1

-50

Returns: 32.780352482431255
50

-50

50

50

-50

Returns: 178.53981633974485

Go vertical, do 90 degree turn, go horizontal
1

0

1000

0

-1000

Returns: 2000.0010000000832

Straight vertical line would be 2000, we get 2000.001.
10

-1

999

-9

-998

Returns: 1997.0410419401694

Points both in negative x area, still cross the wall
50

-30

40

-40

30

Returns: 14.189705460416402

Two points on the circle (same quarter)
50

-30

40

-40

-30

Returns: 78.53981633974483

Two points on the circle (different quarters), so pi/2 * r
50

-10

49

-48

15

Returns: 53.35052970538523

Two points in the same quarter, still have to go around
49

822

174

252

922

Returns: 940.4275623353454
5

-138

903

-529

129

Returns: 867.1545421665045
28

-898

-722

-54

-807

Returns: 848.2694147498188
24

939

-713

858

-713

Returns: 81.0
15

268

637

-561

179

Returns: 947.103479034894
42

-291

816

-503

-991

Returns: 1819.3935802898723
35

-508

-309

207

-492

Returns: 738.047423950521
35

115

204

-402

-81

Returns: 590.3507432027168
42

-391

350

220

-320

Returns: 906.7640266353756
34

951

-814

239

38

Returns: 1574.0371410633607
28

710

-248

427

532

Returns: 1488.840955030168
18

12

-296

241

577

Returns: 930.2082448662138
50

842

661

76

-180

Returns: 1338.6862142094474
17

94

90

338

-621

Returns: 860.6749963270306
14

786

139

680

-288

Returns: 1572.8487484527413
45

990

46

-451

2

Returns: 1443.0522414777201
22

-913

1

850

23

Returns: 1763.2421124076486
39

-21

302

-14

-779

Returns: 1081.9385943615457
8

-8

-117

-5

565

Returns: 682.0079647452374
40

912

-42

-100

-1

Returns: 1019.718976466821
42

-81

-3

1000

-43

Returns: 1090.6484595482195
18

935

299

-112

-609

Returns: 1620.7138339035987
21

702

459

-186

-460

Returns: 1348.3858502101896
39

958

109

-171

-578

Returns: 1614.6210608263605
18

935

-299

-112

609

Returns: 1620.7138339035987
21

702

-459

-186

460

Returns: 1348.3858502101896
39

958

-109

-171

578

Returns: 1614.6210608263605
26

-800

0

91

26

Returns: 891.4225372005919
33

0

303

0

-819

Returns: 1124.4637375158238
11

1000

-12

-56

0

Returns: 1057.0843717825305
24

-45

10

-854

-259

Returns: 852.5502917716937
1

-1

0

-2

-1

Returns: 1.4142135623730951
6

-9

-5

-7

-5

Returns: 2.0
44

-328

33

-746

72

Returns: 419.81543563809083
27

-285

18

-378

27

Returns: 93.43446901438462
38

-882

148

-171

16

Returns: 723.1493621652445
49

-69

12

-831

42

Returns: 762.590322519241
25

-7

24

-15

-20

Returns: 55.35743588970452
13

0

-13

0

13

Returns: 40.840704496667314
29

-29

0

-20

-21

Returns: 23.483723604534838
41

-40

9

158

-41

Returns: 231.47654153485018
50

0

-50

-40

30

Returns: 110.71487177940904
3

3

-4

-2

4

Returns: 11.992631974562693
2

1

-2

2

5

Returns: 10.663618162039253
50

0

50

0

-50

Returns: 157.07963267948966
50

1000

50

1000

-50

Returns: 2157.07963267949
50

1000

50

0

-50

Returns: 1157.0796326794896

Statistics

Problem Statement for "AroundTheWall"

Problem Statement

Definition

Notes

Constraints

Examples