Ssyze'sGeometry

在经过一番学习以后，Ssyze 总算对几何略知一二，所以他想考考你。

在极坐标系下，对于一个以极点为圆心，周长为 l的圆 $\rho(\theta) = \frac{l}{2\pi}$ ，我们可以沿着它的圆周建立一条数轴，使在圆上的每个点 $\left(\rho; \theta \right) = \left(\frac{l}{2\pi}; \frac{2\pi x}{l}\right)$ 都可以用一个实数 x ( $0 \leq x \lt l$ )唯一表示。

现在， Ssyze 在圆上选出了 n 个不同的点，其中第 i 个点的坐标为 $x_i$ 。他想知道，从这 n 个点中任选三个点作为顶点所构成所有三角形中，有多少个包含圆心（在内部或者在边上）？

两个三角形不同，当且仅当他们至少有一个不同的顶点。

#include<bits/stdc++.h> using namespace std; const int maxn=1e6*2+10; typedef long long ll; int n,l; ll ans; int d[maxn]; int main(){ cin>>n>>l; for(int i=1;i<=n;i++)scanf("%d",&d[i]); sort(d+1,d+1+n); for(int i=1;i<=n;i++)d[i+n]=d[i]+l; for(int i=1,j=1;i<=n;i++){ while(j<2*n&&(d[j]- d[i])*2<l)j++; ll an=(j-i-1); ans+=(an-1)*an/2; } ll tot=1ll*n*(n-1)*(n-2)/6; cout<<tot-ans<<endl; }

详情