洛谷 P2181 对角线

本题知识点：
1.任意n边形的凸对角线个数（事实上好像并没有用到）
2.任意凸n边形的对角线交点个数
3.避免数据过大超过变量类型最大值的技巧（数据过大指一堆值相乘再相除，而相乘后数据过大超过范围）

题目描述

对于一个 $n$ 个顶点的凸多边形，它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。

例如，$6$ 边形：

输入格式

输入只有一行一个整数 $n$，代表边数。

输出格式

输出一行一个整数代表答案。

样例 1

样例输入 1

3

样例输出 1

0

样例 2

样例输入 2

6

样例输出 2

15

提示

数据规模与约定

• 对于 $50\%$ 的数据，保证 $3\le n\le 100$。
• 对于 $100\%$ 的数据，保证 $3\le n\le 10^5$。

题解
（先了解什么是凸多边形）
首先，对任意一个凸n边形，其任意一个顶点所能产生的对角线为（n-3）条，所以n个点产生(n-3)n个对角线
，每一个对角线被两个顶点所共有，所以一个凸n边形会产生(n-3)n/2个对角线.
其次，对于任意一个凸多边形，四个顶点产生的对角线若要在图形内相交，必然只能产生一对对角线，所以任取四个不重复的顶点，必然只有一个对角线交点.所以n个顶点，能产生 sum=n!/(4!x(n-4)!) =n(n-1)(n-2)(n-3)/24，
最后，注意到n的取值最大能取到105，四个约等于n的数相乘，必然超过了int和long long的最大限定范围（文末附），所以我们尽量取最大的unsighed long long,最大范围为1.8x10^19。观察到n(n-1)必然可以整除2，n(n-1)(n-2)必然可以被3整除，n(n-1)(n-2)(n-3)必然可以被4整除，故将24分解为2x3x4;num=(n(n-1)/2x(n-2)/3x(n-3)/4),
这样便可以巧妙化解四个数相乘后值超出范围的问题。

完整代码

#include<iostream>
using namespace std;
int main()
{
	unsigned long long n;
	int t;
	int i;
	cin>>n;
	cout <<(n*(n-1)/2*(n-2)/3*(n-3)/4);

	return 0;
}

附常见类型范围：