P2181 对角线——题解

解题思路

任取四个不同顶点，按圆周顺序连接其中两条对角线，会产生唯一一个内部交点；反过来，每个内部交点由两条相交对角线的四个端点唯一确定。因此答案为组合数 $inom n4=n(n-1)(n-2)(n-3)/24$。中间乘积使用 __int128。

正确性说明

四个顶点唯一确定一个凸四边形，其两条对角线恰有一个内部交点；题目保证没有三条对角线共点，所以不同四元组不会对应同一个交点。由双射得到答案 $C(n,4)$。

复杂度分析

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
void print128(__int128 x){if(x>=10)print128(x/10);cout<<char('0'+x%10);}
int main(){long long n;cin>>n;__int128 ans=(__int128)n*(n-1)*(n-2)*(n-3)/24;print128(ans);cout<<'\n';return 0;}

#include <bits/stdc++.h> using namespace std; void print128(__int128 x){if(x>=10)print128(x/10);cout<<char('0'+x%10);} int main(){long long n;cin>>n;__int128 ans=(__int128)n*(n-1)(n-2)(n-3)/24;print128(ans);cout<<'\n';return 0;}