ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Interfering Segment

Ограничение времени: 5.0 секунды
Ограничение памяти: 64 МБ
A triangulation of a polygon P is its partition into non-overlapping triangles whose union is P. In this problem, we put some restrictions on triangulations: all vertices of a triangle must coincide with some vertices of P and no vertex of P must lie on a boundary of a triangle (except for triangle's vertices). We call a segment interfering with a triangulation if it intersects (or touches) a boundary of some triangle of the triangulation.
Your task is, given the polygon P and segment S, to determine whether there exists a triangulation that S does not interfere with. Since it is well-known that all simple polygons can be triangulated, you have only to output the triangle that belongs to some triangulation and contains S strictly inside.

Исходные данные

In the first line there is N (3 ≤ N ≤ 800) — the number of vertices in P.
The following N lines contain pairs of integers (XiYi) — the coordinates of vertices of P in the order of traversal. All points are distinct, and no three consecutive points lie on the same line.
The last line contain four integers Xs, Ys, Xf, Yf — the coordinates of endpoints of S.
All coordinates do not exceed 104 by absolute value. The segment S is guaranteed to lie strictly inside the polygon P. S is also guaranteed to have non-zero length.

Результат

If the solution does exist, output the one-based indices of vertices of triangle that belongs to some triangulation and contains S strictly inside. The indices must be output in a single line and separated by single spaces.
If the solution does not exist, output the word "Impossible" in a single line.

Примеры

исходные данныерезультат
3
0 0
0 3
4 3
1 2 2 2
1 2 3
4
0 0
2 0
2 3
0 3
1 1 1 2
Impossible
Источник задачи: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1626. Interfering Segment