洛谷 P2181 对角线
题目描述
对于一个 个定点的凸多边形,他的任何三条对角线都不会交于一点。请求图形中对角线交点的个数。
例如,六边形:
输入格式
第一行一个 ,代表边数。
输出格式
第一行输出交点数量
输入输出样例
输入1
3
输出1
0
输入2
6
输出2
15
说明/提示
$50\%$ 的测试数据 $3\leqslant n\leqslant100$; $100\%$ 的测试数据 $3\leqslant n\leqslant 100000$。分析
由于任何三条对角线不会交于一点,故对于每一个交点,只有两条对角线经过,所以一个交点与四个顶点相关联,即四个顶点确定一个交点,答案为。直接这样算用```unsigned long long``也会爆,所以可以将式子改写为$\frac{{\frac{{\frac{{n(n - 1)}}{2} \times (n - 2)}}{3} \times (n - 3)}}{4}$。
代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 11D_Beyonder's Blog!