n辺形対角線交点問題

3199 ワード

1つのn個の頂点の凸の多角形について、そのいずれの3本の対角線も1点に交差しないで、対角線の交点の個数を求めます
四角形の対角線交点の個数は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;
}