洛谷P2181 对角线

P2181 对角线

以每个顶点为基准,以(n=6)为例,三条对角线与其他对角线交点个数分别为(3+4+3=10),将(10*n(6)=60),那么每个交点计算了(4)次(每个交点的两条线段各计算一次,一条线段会被计算两次)

计算每个顶点出发的对角线与其他线段交点个数,容易发现

[sum=sum_{i=1}^{n-3}i*(n-2-i) ]

[sum=(n-2)sum_{i=1}^{n-3}i-sum_{i=1}^{n-3}i^2 ]

[ans=sum*n÷4 ]

我草题解好奥妙啊

根据上述分析每四个顶点确定一个交点

[ans=dbinom{n}{4} ]

原文地址:https://www.cnblogs.com/knife-rose/p/14891752.html