《算法竞赛宝典》基础算法艺术(公开课程)

【问题描述】凸多边形的三角形剖分（triangle.cpp/c/pas）

传说魔法世界的创世神使用过的一件上古神器遗失在一个凸多边形的二维魔法空间中，谁若拥有这件上古神器，将会成为世界之主。修罗王很想拥有这件上古神器，他打算通过若干条互不相交的对角线，把这个多边形剖分成了若干个三角形来寻找，现在的任务是输入凸多边形的边数n，求不同剖分的方案数C_n。比如当n=5时，如图所示，有如下5种不同的方案，所以C₅=5。

【输入格式】

一个整数n。

【输出格式】

一个整数，即方案数。

【输入样例】

5

【输出样例】

5