Triangulation#5958
A polygon with vertices is provided. This polygon has no self-intersections or self-tangencies. Your task is to triangulate the polygon, meaning you need to divide it into exactly N-2 triangles, ensuring the following conditions are satisfied:
The vertices of each triangle must be selected from the vertices of the original polygon.
Each triangle must be non-degenerate.
Each triangle must be completely contained within the original polygon.
The interior regions of any two triangles must not overlap.
The first line contains the integer (3 \leq N \leq 5000), representing the number of vertices of the polygon. The next lines each contain two integers: x_i,\ y_i (-10000 \leq x_i,\ y_i \leq 10000), which are the coordinates of the polygon's vertices listed in counterclockwise order. It is guaranteed that all points are distinct. Furthermore, any pair of sides shares exactly one common point if they are adjacent, and none otherwise.
Output N-2 lines, each containing three distinct integers: a_i,\ b_i, and c_i (1 \leq a_i,\ b_i,\ c_i \leq N). These integers are the indices of the vertices of the original polygon that form the -th triangle. The vertices of the polygon are numbered starting from in the order they appear in the input.
If multiple triangulation solutions exist, any valid one can be provided. Triangles can be listed in any order, and the indices of the vertices within each triangle can also be in any order.
Example 1