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

练python刷简单题刷到了这个，挺有趣的一道题目。

对于一个 (n) 边形，选任意一个点A可以引出(n-3)条对角线。相邻的点B再引出(n-3)条线，分别与前者有(1,2 ... n-3)个交点。与B相邻且不与A相邻的C引出(n-4)条线，交A引出的对角线有(1,2 ... n-4)个交点，B亦然。

有一篇论文介绍得十分详细 链接

故结果应为(sumlimits^{n-3}_{i=1}(i*sumlimits^{n-2-i}_{j=1})quad= quadsumlimits^{n-3}_{i=1}i*frac{(n-i-1)(n-i-2)}{2})

代码如下

n=int(input())
ans=0
i=1
while True :
    ans+=i*(n-(2+i))*(n-(1+i))//2
    if n-(1+i)<=2 :
        break
    i+=1
print(ans)

此方法可以解决这个问题，时间复杂度(O(n))

2

我暂时不会对上述和式求和，但推测通项可能是或四次的。故希望能(O(1))解决这个问题。

令(f(n)=sumlimits^{n-3}_{i=1}frac{(n-i-1)(n-i-2)}{2}) 易知(f(3)=0,f(4)=1,f(5)=5,f(6)=15,f(7)=35)
构建范德蒙德矩阵

验证(n>=8)，成立。则

使用matlab计算这个问题

>> format rat
>> V=vander([3 4 5 6 7]);
>> inv(V)*[0;1;5;15;35]

ans =

       1/24    
      -1/4     
      11/24    
      -1/4     
      -1/25588634246423

所以代码为此简单的三行

a=int(input())
a=a*a*a*a-a*a*a*6+a*a*11-a*6
print(a//24)

3

实际上，用组合数学的方法，我们知道，每四个不同的顶点有一个交点，答案即是(C^{4}_n=frac{n(n-1)(n-2)(n-3)}{24})与以上结果相同。