n辺形対角線交点問題
3199 ワード
1つのn個の頂点の凸の多角形について、そのいずれの3本の対角線も1点に交差しないで、対角線の交点の個数を求めます
四角形の対角線交点の個数は1つしかないことを知っているので,この問題はこのn辺形がどれだけ四角形があるかを求めることに転化した.n個の頂点、順番に4個の頂点を取って、組み合わせ数の公式C(n,4)を使います.
四角形の対角線交点の個数は1つしかないことを知っているので,この問題はこのn辺形がどれだけ四角形があるかを求めることに転化した.n個の頂点、順番に4個の頂点を取って、組み合わせ数の公式C(n,4)を使います.
/* n , 。 。*/
#include
int main()
{
/* , unsigned*/
unsigned long long vertex, intersec;
scanf("%llu", &vertex);
/* , ,
C(n,4) = intersec = (vertex * (vertex - 1) * (vertex - 2) * (vertex - 3)) / 24;
n long long, */
intersec = vertex * (vertex - 1) / 2 * (vertex - 2) / 3 * (vertex - 3) / 4;
if (vertex <= 3)
{
intersec = 0;
}
printf("%llu", intersec);
return 0;
}