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

SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Interfering Segment

Time limit: 5.0 second
Memory limit: 64 MB
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
Problem Source: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.
To submit the solution for this problem go to the Problem set: 1626. Interfering Segment