|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||256 MB||0||0||0||0.000%|
There is a variety of navigation problems around us. This is a problem about an algorithm called Bug2.
Bug algorithms solve the following navigation problem. There is a two-dimensional map containing obstacles of an arbitrary shape, and start and finish points are given. There is also an “agent”, who initially stands at the start point S, and its task is to reach the finish point F. It knows the coordinates of the finish point, and at any moment of time it can determine its own coordinates. The agent has O(1) memory, so it cannot store the map of obstacles. The only way it can get information about the outer world is to detect whether it touches an obstacle. The Agent is able to move around the obstacle following its boundary. The problem is to reach the finish point when it is possible, and correctly report the fact of unreachability otherwise.
The Bug2 algorithm, which belongs to the family of Bug algorithms, works as follows:
One may prove the correctness of an algorithm, that is, that it reaches the finish point in finite time (that is, the length of the resulting path is finite) if it is possible, and reports that the finish point is unreachable in finite time otherwise.
Given a set of polygonal obstacles, a start and a finish point, determine the length of the path that an agent directed by Bug2 algorithm will traverse.
The first line of the input file contains five integer numbers n, xS, yS, xF, yF — the number of obstacles and the coordinates of start and finish points.
The rest of the input file describes obstacles. Each description starts with a line containing an integer m (m ≥ 3) — the number of vertices in the obstacle. The following m lines contain pairs of integer numbers xi, yi — the coordinates of vertices of the obstacle, given in the clockwise direction. The obstacle does not have self-intersections or self-tangencies.
The total number of vertices in all the obstacles does not exceed 300 000. No coordinate exceeds 106 by an absolute value.
No vertex of an obstacle lies on a line SF. Both start and finish point will lie strictly outside any obstacle. No two obstacles share common points. If there are two points A and B where obstacle boundaries intersect with the line SF, either |AF| = |BF| or|AF| − |BF| > 10−6 will be true.
Output the length of a path traversed by the agent directed by the described algorithm. The absolute or relative error of 10−6 is acceptable.
1 0 2 6 2 8 1 0 1 3 2 3 2 1 4 1 4 3 5 3 5 0