Delaunay triangulation
Triangulation of a set of points on the plane is a set of nondegenerate triangles satisfying the following conditions:
Vertices of the triangles are the only points of the original set. Each point is the apex of the initial set of at least one triangle.
Two different triangle or have no common points, or have a common vertex, or have a common side (but the area of their intersection is always 0).
Any point inside the convex hull of the original set of points belongs to at least one triangle (it may belong to several triangles, if it is their common vertex or belongs to their common side). (The convex hull of a set of points is the smallest convex polygon containing all these points).
Triangulation is Delaunay triangulation, if, in addition, it satisfies the following condition:
Inside the circle circumscribed around any triangle of the triangulation is not none of the starting points (the points can lie on the circle, in particular for her, obviously, are considered the top of the triangle).
For a given set of points of its search for the Delaunay triangulation (two triangulations are different if they differ by at least one triangle).
Input
The first line of the input file contains the number N – the number of points (3 ≤ N ≤ 30), the initial set. The next N lines each contain a pair of real numbers - the corresponding location. No three points lie on a straight line.
Output
Bring in the output of various triangulation of this set of points.