题目描述

对于一个 nn 个定点的凸多边形，他的任何三条对角线都不会交于一点。请求图形中对角线交点的个数。
例如，六边形：

输入格式

第一行一个 nn，代表边数。

输出格式

第一行输出交点数量

输入输出样例

输入1

3

输出1

0

输入2

6

输出2

15

说明/提示

$50\%$ 的测试数据 $3\leqslant n\leqslant100$; $100\%$ 的测试数据 $3\leqslant n\leqslant 100000$。

分析

由于任何三条对角线不会交于一点，故对于每一个交点，只有两条对角线经过，所以一个交点与四个顶点相关联，即四个顶点确定一个交点，答案为Cn4=n(n−1)(n−2)(n−3)24C_n^4=\frac {n(n-1)(n-2)(n-3)}{24}。直接这样算用```unsigned long long``也会爆，所以可以将式子改写为$\frac{{\frac{{\frac{{n(n - 1)}}{2} \times (n - 2)}}{3} \times (n - 3)}}{4}$。

代码

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int main()
{
    unsigned long long n;
    cin>>n;
    unsigned long long ans=n*(n-1)/2*(n-2)/3*(n-3)/4;
    cout<<ans<<endl;
    return 0;
}