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

1626. 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.


исходные данныерезультат
0 0
0 3
4 3
1 2 2 2
1 2 3
0 0
2 0
2 3
0 3
1 1 1 2
Источник задачи: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.