W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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:
4
Task author: Krzysztof Diks.