Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Олимпиадные задачи на английском языке

19/11/2007 | Тренировка (задачи ACM ICPC Asia RC Tokyo 2007) (E) |

*Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Your task in this problem is to create a program that finds the shortest path between two given
locations on a given street map, which is represented as a collection of line segments on a plane.

Figure 1: An example map

Figure 1 is an example of a street map, where some line segments represent streets and the
others are signs indicating the directions in which cars cannot move. More concretely, AE, AM,
MQ, EQ, CP and HJ represent the streets and the others are signs in this map. In general, an end
point of a sign touches one and only one line segment representing a street and the other end
point is open. Each end point of every street touches one or more streets, but no signs.

The sign BF, for instance, indicates that at B cars may move left to right but may not in the
reverse direction. In general, cars may not move from the obtuse angle side to the acute angle
side at a point where a sign touches a street (note that the angle CBF is obtuse and the angle
ABF is acute). Cars may directly move neither from P to M nor from M to P since cars moving left
to right may not go through N and those moving right to left may not go through O. In a special
case where the angle between a sign and a street is rectangular, cars may not move in either
directions at the point. For instance, cars may directly move neither from H to J nor from J
to H.

You should write a program that finds the shortest path obeying these traffic rules. The length
of a line segment between `(x_1,\ y_1)` and `(x_2,\ y_2)` is
`sqrt{(x_2\ -\ x_1)^2\ +\ (y_2\ -\ y_1)^2}`.

The input consists of multiple datasets, each in the following format.

`n`

`x_s\ y_s`

`x_g\ y_g`

`x_1^1\ y_1^1\ x_2^1\ y_2^1`

`***`

`x_1^k\ y_1^k\ x_2^k\ y_2^k`

`***`

`x_1^n\ y_1^n\ x_2^n\ y_2^n`

`n`, representing the number of line segments, is a positive integer less than or equal to 200.

`(x_s,\ y_s)` and `(x_g,\ y_g)` are the start and goal points, respectively. You can assume that `(x_s,\ y_s)\ ≠\ (x_g,\ y_g)` and that each of them is located on an end point of some line segment representing a
street. You can also assume that the shortest path from `(x_s,\ y_s)` to `(x_g,\ y_g)` is unique.

`(x_1^k,\ y_1^k)` and `(x_2^k,\ y_2^k)` are the two end points of the `k`th line segment. You can assume that
`(x_1^k,\ y_1^k)\ ≠\ (x_2^k,\ y_2^k)`. Two line segments never cross nor overlap. That is, if they share a point, it
is always one of their end points.

All the coordinates are non-negative integers less than or equal to 1000. The end of the input
is indicated by a line containing a single zero.

For each input dataset, print every street intersection point on the shortest path from the start point to the goal point, one in an output line in this order, and a zero in a line following those points. Note that a street intersection point is a point where at least two line segments representing streets meet. An output line for a street intersection point should contain its `x`- and `y`-coordinates separated by a space.

Print `-1` if there are no paths from the start point to the goal point.

Sample Input

8 1 1 4 4 1 1 4 1 1 1 1 4 3 1 3 4 4 3 5 3 2 4 3 5 4 1 4 4 3 3 2 2 1 4 4 4 9 1 5 5 1 5 4 5 1 1 5 1 1 1 5 5 1 2 3 2 4 5 4 1 5 3 2 2 1 4 2 4 1 1 1 5 1 5 3 4 3 11 5 5 1 0 3 1 5 1 4 3 4 2 3 1 5 5 2 3 2 2 1 0 1 2 1 2 3 4 3 4 5 5 1 0 5 2 4 0 4 1 5 5 5 1 2 3 2 4 0

Output for the Sample Input

1 1 3 1 3 4 4 4 0 -1 5 5 5 2 3 1 1 0 0