A regular n-sided polygon P can be partitioned into n − 2 triangles by adding non-crossing line segments connecting two vertices of P. For example, a square can be partitioned into two triangles, a regular pentagon can be partitioned into three triangles, and a regular hexagon can be partitioned into four triangles. The resulting set of triangles is called a triangulation of P. There exist two or more triangulations of P if n is greater than three.

Once a triangulation T of P is chosen, the distance between two triangles a and b in T is defined to be the number of hops crossing the borders of two adjacent triangles when you travel from a to b. Note that you must stay inside the polygon P, at any time during this travel, that is, it is not allowed to hop crossing the border of P.

For example, the distance of a and d in the triangulation shown in Figure J.1 is three since the triangles, a, b, c, and d, should be visited to travel from a to d, and you have to hop three times crossing borders between triangles.

The diameter of a triangulation T is the maximum of the distances between all pairs of triangles in T. Write a program to find a triangulation of a regular n-sided polygon P whose diameter is the minimum over all possible triangulations and print its diameter.

#4393 upload 2 done 2 how_to_reg 2

Triangulation timer 1s memory 512MB

#4393

Triangulation 1s 512MB