Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2568
Counting Triangulations

Time Limit: 10 Seconds      Memory Limit: 32768 KB

The triangulation of the set of the points on the plane is the set of triangles, satisfying the following conditions:
1. no triangle is degenerate;
2. no two triangles have a common interior point (common border points are allowed);
3. all vertices of each triangle are the points from the given set;
4. each point within the convex hull of the given points belongs to some triangle;
5. no point of the given set belongs to the interior of a triangle.

A set of triangles is called pretriangulation if it satisfies all these conditions except possibly the last. A pretriangulation is called minimal if it contains minimal possible number of triangles among all pretriangulations of the given set. A triangulation is called consecutive if it can be obtained from some minimal pretriangulation by successively applying the following split operation: choose a point that belongs to the interior of some triangle and connect it to the vertices of this triangle, splitting it to three smaller ones. Given the set of the points on the plane, no three of which are lying on the same line, find the number of its consecutive triangulations. Two triangulations are different if they are different as sets of fixed triangles.


The first line of the input file contains n -- the number of points (3 <= n <= 50). The following n lines contain two integer numbers each -- coordinates of the points (no coordinate exceeds 10000 by its absolute value).


Output the number of different consecutive trianguations of the given points set.

Sample Input:
0 0
3 3
3 0
0 3
0 0
3 3
3 0
2 1
Sample Output:

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4
Submit    Status