#include<iostream>
using namespace std;
int main()
{
    unsigned long long n;
    cin >> n;
    cout << n * (n - 1)/2*(n-2)/3*(n-3)/4 << endl;
    system("pause");
    return 0;
}

数据规模

对于100%的数据，3<=n<=10^5

unsigned long long 的范围为10^19次方左右

每个n的最大数据规模为10^5左右，式子中大概为n^4即大约为10^19次方左右，采用unsigned long long.

对角线公式：n（n-3）/2

由于求对角线的交点，三边形不存在对角线，即无对角线交点

四边形有两条对角线，对角线交点数为1

对角线交点数公式解释：

但可能会出现WA爆掉的情况

可以将公式化简

n * (n - 1)/2*(n-2)/3*(n-3)/4

第三篇题解

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

例如，6 边形：

输入格式
输入只有一行一个整数 nn，代表边数。

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

输入输出样例
输入 3 输出 0
输入 6 输出 15

数据规模与约定

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

个人理解：这题实际上有公式，但这雨我无瓜，我不知道这个公式，说到底还是因为菜。

所以我还是研究了一下公式解法

way1:

公式讲解 ：首先我们知道两个对角线相交有且仅有一个交点，而四边形有且仅有两条对角线，也就是说两条对角线确定了四个顶点。因此！！！如果有n个顶点，需要选出4个顶点，这就涉及到了高中的排列组合，这道题是组合问题！因为选的顺序又不影响构成的对角线个数。然后，就套公式啦！

n * (n-1) * (n-2) * (n-3) / 4!

但是，我这样提交洛谷直接给我WA，哭唧唧

然后，在 我的不懈努力 借鉴大佬经验下，得出结论，爆掉了… long long 改成 unsigned long long 都不行… 把上面的公式改成

n * (n-1)/2 * (n-2)/3 * (n-4)/4

即可。大佬不愧是大佬（此处应该有掌声）

#include<stdio.h>
int main(){
	unsigned long long n,sum;
	scanf("%lld",&n);
	sum=n*(n-1)/2*(n-2)/3*(n-3)/4;
	//sum=n*(n-1)*(n-2)*(n-3)/24;
	printf("%lld\n",sum);
	return 0;
}

下面介绍一下不会公式法

way2:

推算“笨”方法：

接下来就是小学奥数熟悉的找规律，相邻两个交点数做差，反复做差。
最开始是，1，4，10，20，35，56…
然后，1，3，6，10，15，21…
接着，1，2，3，4，5，6…
这相邻俩交点的关系不久清晰了嘛

#include<stdio.h>
long long a1[100000];//题目中要求了数据规模10^5
long long a2[100000];//回顾了一下数组的知识！
long long a3[100000];//定义longlong是怕数据溢出！
int main()
{
	long long n,i;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		a1[i]=a1[i-1]+i;//这里生成1,3,6,10序列
	}
	for(int i=1;i<=n;i++)
	{
		a2[i]=a2[i-1]+a1[i];//这里生成1,4,10,20序列
	}
	for(int i=1;i<=n;i++)
	{
		a3[i]=a3[i-1]+a2[i];//这里生成答案序列：1,5,15,35
	}
	printf("%lld",a3[n-3]);
	//举个栗子:当n为6时,a3[6]实际对应的是n=9的值,所以一定注意减三!!!
	return 0;
}

over

这图看着就让人开心！

如有错误，欢迎指出！

一周半前开始帮老师写东西，到今早一点才完成，还只是初稿，拖欠不少作业，博客也鸽了，先补一篇。

import java.io.IOException;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException{
		Scanner sc=new Scanner(System.in);
		String n=sc.next();
		BigInteger a,b,c,d,e,f,g,h;
		a=new BigInteger(n);
		b=new BigInteger("1");
		c=a.subtract(b);//n-1
		d=c.subtract(b);//n-2
		e=d.subtract(b);//n-3
		f=e.multiply(d).multiply(c).multiply(b).multiply(a);//n(n-1)(n-2)(n-3)
		g=new BigInteger("24");
		h=f.divide(g);
		System.out.println(h);
	}
}

思路：两条对角线确定一个交点，四个顶点确定两条相交的对角线，所以就是无顺序的从顶点中取四个顶点，也就是组合数C下面写个n，上面写个4。
由于n<=10^5，因此需要BigInteger类。
BigInteger类：


注意输入时用string类接收。