ZOJ Problem Set - 2568
The triangulation of the set of the points on the plane is the set of triangles, satisfying the following
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:
4 0 0 3 3 3 0 0 3 4 0 0 3 3 3 0 2 1Sample Output:
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4