High School Programming League Problems Archive

After the last robbery in the Museum of Natural History, a modern anti-theft alarm has been installed. Many people have volunteered to test the system, but so far none of them have managed to break it. Now, the management of the museum has changed their approach and they would like someone to find the weakest points of the system. They have asked you for help. Write a program which will find a route to the main exhibit such that the probability of being detected is the smallest possible. To do so, you have been given a map of the exhibition room.

• The floor consists of square tiles.
• There are other exhibits in the room – the thief cannot step on them.
• The thief can only move in four directions: up, down, left, and right (U, D, L, R),
• The starting point of the route is fixed – it is the position of a ventilation hole. The endpoint is also fixed – it is the position of the main exhibit.
• There are temperature sensors which have 100% detection efficiency at their location. The further from the sensor the thief is, the smaller the efficiency of the sensor. Its distribution is linear, up to integer rounding of the percentage value.
• If a tile is within the range of more than one sensor, then the probability of being detected is the maximum of the detection efficiencies of the particular sensors.
• There can be both a sensor and an exhibit at the same location.

Input

The input description is almost the same as in the Mowing Optimization problem. First, we are given the starting point (x1, y1) - the potential thief is located at (x1, y1) (x1+1, y1) (x1+1, y1+1) (x1, y1+1), and the end point (x2, y2)

Next, there is given a description of the border of the room which consists of: an integer k – the number of line segments (4 <= k <= 1000), then there come the descriptions of successive segments of the boundary, expressed by the coordinates of one distinguished point (a, b), followed by k vectors[ a_i, b_i] separated by commas, describing the i -th segment of the border when traversed in the clockwise direction (for each i , 1<= i <= k we have 0 < a_i² +b_i² < 10⁶ and a_ib_i=0).

Then there is given n - the number of other exhibits in the room and then there are n descriptions of every exhibit (i.e., the coordinates of the starting point and of the outline, as above). Then there is given d – the number of sensors, followed by d descriptions of each sensor (x, y) r, where r is the range of detector. Position is determined in the same way as the starting and ending point - sensor is placed in the centre of a tile.

You can assume that each outline is a closed line, in which no two segments cross, nonadjacent elements do not touch themselves, the total number of tiles to be cut does not exceed 10000, and the whole room fits into a 1000x1000 square.

Output

First, output a single integer, describing the number of steps to be made, followed by a sequence of letters describing the successive steps. After all the steps have been completed, the thief should be located at the main exhibit point. If the thief will step onto another exhibit or a temperature sensor, your solution will be deemed incorrect. Likewise, your solution will be incorrect if at any time the theft will be located outside the room. If more than one possible route exists, you should output any one of them.

Example description

• white - normal tile
• black – other exhibits
• blue point - start
• violet point –target
• red – a temperature sensor
• orange, yellow –range of a sensor

Example 1

Input:
(0, 0) (3, 3)
4
(0, 0), [0, 4], [4, 0], [0, -4], [-4, 0]
0
2
(0, 3) 2
(3, 0) 4

Output:
6
URURUR

Example 2

Input:
(0, 0) (2, 5)
6
(0, 0), [0, 6], [6, 0], [0, -5], [-3, 0], [0,-1], [-3, 0]
2
6
(1, 3), [0, 2], [2, 0], [0, -1], [-1, 0], [0, -1], [-1, 0]
4
(4, 2), [0, 2], [1, 0], [0, -2], [-1, 0]
2
(0, 5) 2
(3, 2) 4


Output:
13
URRRRRUUUULLL

Scoring

For solving this problem you will score 10 points.