AroundTheWall

TCO17 Austin · 2017-03-31 · by Nickolas

TCO17 Austin · 2017-03-31 · by Nickolas · Geometry

Show categories

Class Name: AroundTheWall

Return Type: double

Method Name: minDistance

Arg Types: (int, int, int, int, int)

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.

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

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.

10)

50
1000
1000
1000
-1000
Returns: 2908.734892250384

Max answer

13)

1
-1000
-1000
1000
1000
Returns: 2828.4278318530005

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

18)

50
-50
50
50
-50
Returns: 178.53981633974485

Go vertical, do 90 degree turn, go horizontal

19)

1
0
1000
0
-1000
Returns: 2000.0010000000832

Straight vertical line would be 2000, we get 2000.001.

20)

10
-1
999
-9
-998
Returns: 1997.0410419401694

Points both in negative x area, still cross the wall

21)

50
-30
40
-40
30
Returns: 14.189705460416402

Two points on the circle (same quarter)

22)

50
-30
40
-40
-30
Returns: 78.53981633974483

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

23)

50
-10
49
-48
15
Returns: 53.35052970538523

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

Submissions are judged against all 71 archived test cases, of which 17 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AroundTheWall with a public method double minDistance(int r, int x1, int y1, int x2, int y2) · 71 test cases · 2 s / 256 MB per case