首页 > 技术文章 > 洛谷P2181 对角线

knife-rose 2021-06-17 00:55 原文

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} \]

推荐阅读