In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
We say that two triangles intersect if their interiors have at least one common point. A polygon is called convex if every segment connecting any two of its points is contained in this polygon. A triangle whose vertices are also vertices of a convex polygon is called an elementary triangle of this polygon. A triangulation of a convex polygon is a set of elementary triangles of this polygon, such that no two triangles from the set intersect and a union of all triangles covers the polygon.
We are given a polygon and its triangulation. What is the maximal number of triangles in this triangulation that can be intersected by an elementary triangle of this polygon?
Consider the following triangulation:
The elementary triangle intersects all the triangles in this triangulation.
Write a program that:
In the first line of the standard input there is a number , , which equals the number of vertices of the polygon. The vertices of the polygon are numbered from to clockwise.
The following lines describe the triangles in the triangulation. There are three integers separated by single spaces in the -st line, where . These are the numbers of the vertices of the -th triangle in the triangulation.
In the first and only line of the standard output there should be exactly one integer — the maximal number of triangles in the triangulation, that can be intersected by a single elementary triangle of the input polygon.
For the input data:
6 0 1 2 2 4 3 4 2 0 0 5 4
the correct result is:
Task author: Krzysztof Diks.