ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1199. Mouse

Time limit: 2.0 second
Memory limit: 64 MB
In the kitchen lives a mouse. There are also a cat and a piece of cheese in the kitchen. The coordinates of the cheese and the mouse are known, and the cat is sleeping. Finally, there is some furniture in the kitchen. The furniture is a set of convex polygons. The mouse wants to get to the cheese unnoticed. A point of the route is called dangerous if the distance to the nearest piece of furniture is greater than 10 cm. It is required to find the least dangerous route for the mouse, i.e., the route in which the sum of the lengths of dangerous segments is minimal.


In the first line there are four numbers xm, ym, xc, yc separated with a space. They are the coordinates of the mouse (xmym) and of the cheese (xcyc). In the second line there is the number of pieces of furniture N (0 ≤ N ≤ 100). The next N lines describe these pieces. Each description starts with the number of vertices of the corresponding polygon K (3 ≤ K ≤ 10), given in a separate line. Each of the next K lines contains two numbers, which are the coordinates of the corresponding vertex. It is known that the distance between any two points of different polygons is greater than 20 cm (so that it would be easier for the cat to catch the mouse). Neither the mouse nor the cheese are inside any of the polygons. All the coordinates are given in meters and have no more than three fractional digits. The absolute values of coordinates do not exceed 105.


You should give the mouse’s route in the form of a broken line. In the first line output the number of its vertices (including the initial and final ones). Then give the coordinates of the vertices, two numbers per line, accurate to 10-4. Each segment of the broken line must be either entirely dangerous or entirely safe (with the possible exception of its endpoints). The broken line must contain no more than 1000 vertices.


1.0 1.5 0.0 1.5
0.0 0.0
0.0 1.0
1.0 1.0
1.0 0.0
1.0 1.5
1.0 1.1
0.0 1.1
0.0 1.5
Problem Author: Nikita Rybak