Delaunay triangulation#2188

Delaunay triangulation

1 second
64 megabytes
Hard

Triangulation of a set of points on the plane is a set of nondegenerate triangles that satisfy the following conditions:

  1. The vertices of the triangles are only the points of the original set. Each point of the initial set is the vertex of at least one triangle.

  2. Any two different triangles either have no points in common, share a common vertex, or share a common side (but the area of their intersection is always ).

  3. Any point located 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 a common vertex or lies on a common side). (The convex hull of a set of points is the smallest convex polygon containing all the points).

A triangulation is called a Delaunay triangulation if, in addition, the following condition is satisfied:

For the given set of points, determine the number of its Delaunay triangulations (two triangulations are considered different if they differ by at least one triangle).

Input

The first line contains the number (3 \leq N \leq 30), the number of points in the set. Each of the next lines contains a pair of real numbers — the coordinates of the corresponding point. No three points lie on a straight line.

Output

Output the number of different Delaunay triangulations of the given set of points.

Examples

Example 1

Loading
Loading