L. Wheelchair (1000 points)

Even completely normal use of a motorbike - according to all road laws and regulations - can be quite dangerous. Doing wheelies at high speed in between of heavy artillery is not the best life insurance policy. Bertie and his gang are aware of the dangers, and they're conscious of - among other things - wheelchair accessibility of public buildings.

Navigating a badly designed building in a wheelchair can be an arduous undertaking. Your task here is to find short paths through mazes using a wheelchair. Apparently the architects of these mazes haven't considered wheelchair accessibility their first concern...

The mazes are sets of walls, as line segments in two dimensions. The wheelchair has an initial position and orientation, and a given target point. To solve a maze, the wheelchair may be pushed forward or backward, and turned around either wheel, finally to reach the vicinity of the target point - without having the wheelchair intersect any walls.

The Wheelchair

The collision zone of the wheelchair is modeled using two line segments for the wheels, and one rectangle for the body (and the legs of the user).

The origin point of the wheelchair's coordinate system is the intersection of the wheel axis and the centerline.

The wheels are parallel; their distance is 1 unit. Their diameter (the length of the line segments) is 1.

The body rectangle is 0.5 wide and 1 long (along the centerline). It is positioned exactly between the wheels. Its longer side begins right at the wheel axis, and ends 1 unit forward - thus the resulting bounding box of the wheelchair is 1 unit wide and 1.5 units long.

Input Format

• Line 1: wall_cnt chair_x chair_y chair_dir target_x target_y
• Lines 2 .. (wall_cnt+1): wall_x1 wall_y1 wall_x2 wall_y2

Where:

• wall_cnt (integer) number of wall segments
• chair_x, chair_y (float) initial position of wheelchair (origin point)
• chair_dir (float) initial direction of wheelchair
• target_x, target_y (float) position of target point
• wall_x1, wall_y1, wall_x2, wall_y2 (float) wall segment coordinates

Direction is given in radians. 0.0 points "east" (X positive), π/2 points "north" (Y positive).

Output Format

The output is a series of actions for the wheelchair that gets it to the target point without running into any walls on the way. One action goes on one line. Each line should consist of an action letter, a single space, then a float amount.

Available actions:

• Push (P n): push wheelchair forward by n units. Negative amount pulls the wheelchair backwards.
• Left (L n): lock left wheel, turn wheelchair counterclockwise around left wheel by n radians.
• Right (R n): lock right wheel, turn wheelchair counterclockwise around right wheel by n radians.

The turning actions rotate the wheelchair around the centerpoint of the specified wheel, by the specified amount. The wheel's centerpoint stays in place, but the origin of the wheelchair will change (describing an arc with r=0.5 around the wheel's centerpoint). Maximum allowed turning amount is +/- 2 π.

During pushes and turns, the collision zones of the wheelchair may not intersect a wall segment, at any point in time (i.e. not only the end position and orientation should be considered).

After the last action, the wheelchair's origin must be within 0.5 units from the target point.

Scoring

This task uses scaled scoring, based on the wheelchair's traveled distance. For each input, the solution with the shortest traveled distance gets maximum score (100 points).

The traveled distance is calculated using the wheelchair's origin point as reference.

Sample Input

2 2 3 -1.57079632679 4.5 3
1 1 3 1
3 1 3 5

A graphical interpretation of the above input:

Sample Output

P -4
L 1.57079632679
P 1.5
R -1.57079632678
P 3

Explanation:

1. Pull wheelchair back 4 units
2. Lock left wheel, rotate around left wheel counterclockwise by 90° (π/2)
3. Push wheelchair forward 1.5 units
4. Lock right wheel, rotate around right wheel clockwise by 90° (π/2)
5. Push wheelchair forward 3 units

A graphical interpretation:

Outline of wheelchair collision zones on this path:

Floating Point Disclaimer

This task involves a lot of FP calculations, and as such, there may be inaccuracies. If your solution barely evades a wall by a nanounit in your calculations, in our evaluator it may just barely intersect it; thus it may be advisable to leave a bit of breathing room. To assist in debugging such problems, our evaluator will report the position and nature of collisions in failure messages.