[XSY3381] 踢罐子（几何）

XSY3381

点被选为点对之一的贡献我们单独计算（这部分贡献的总和为$4n(n-1)(n-2)$）。接下来只讨论剩余部分的贡献。

先把任意三个点构成的六种选择方案合并，发现在外接圆周和弦之间的点每个有2的贡献，在外接圆上的点每个有1的贡献。

然后考虑任意四个点$A,B,C,D$的贡献。
发现当四个点构成凸四边形$ABCD$时，
若$\angle A+\angle D=180°$：
$A,B,C,D$四点共圆，即其中一个点在另外三个点构成的三角形的外接圆上，因此$A,B,C,D$四个点每个有1的贡献，$A,B,C,D$四点的贡献为4。

若$\angle A+\angle D<180°$：
则必有$\angle B+\angle C>180°$。
$D$在$△ABC$的外接圆外，选$A,B,C$为点对时，$D$无贡献。同理$A$无贡献。
$B$在$△ACD$的外接圆弧和弦之间，选$A,C,D$为点对时，$B$有2的贡献。同理$C$有2的贡献。$A,B,C,D$四点的贡献为4。

若$\angle A+\angle D>180°$：
则必有$\angle B+\angle C<180°$。类似上种情况。

当四个点构成凹四边形时，易证四个点产生的贡献为0。

因此问题转化为统计凸四边形个数。

给出四个构成凸四边形的点，任选两个点连边，有4种情况剩下两个点在连边同侧，2种情况剩下两个点在连边异侧。

给出四个构成凹四边形的点，任选两个点连边，有3种情况剩下两个点在连边同侧，3种情况剩下两个点在连边异侧。

因此设整张图中有$a$个凸四边形，$b$个凹四边形，
$$X=\sum _{i<j}i,j连边，再无序地选两个点，选的点在连边同侧的方案数$$
$$Y=\sum _{i<j}i,j连边，再无序地选两个点，选的点在连边异侧的方案数$$

可列出方程：
$$\{\begin{array}{l}4a+3b=X\\ 2a+3b=Y\end{array}$$

解得：

$$a=\frac{X-Y}{2}$$

具体实现上，
对于每个点，把剩下的所有点按照和它的连线的斜率排序，求斜率可以用$atan2l$函数（加上$l$避免爆精度）

然后，考虑两个点的连线，设连线两侧的点数分别是$L$和$R$（注意这里要判断，不能构成了一个箭头的形状）

选两个点在连线同侧的有$\frac{(L-1)L+(R-1)R}{2}$种情况，选两个点在连线异侧的有$L\times R$种情况。

时间复杂度$O(n^{2}logn)$

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define pi acos(-1) using namespace std; typedef long long ll; const int N=2010; int n,tot; double x[N],y[N],k[N]; ll ans=0; int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int main(){n=read();for(int i=1;i<=n;i++){x[i]=read();y[i]=read();}ans=4ll*n*(n-1)*(n-2);for(int i=1;i<=n;i++){tot=0;for(int j=1;j<=n;j++){if(i==j) continue;k[++tot]=atan2l(x[j]-x[i],y[j]-y[i]);if(k[tot]<0) k[tot]+=pi*2;}sort(k+1,k+tot+1);for(int j=1;j<=tot;j++){k[j+tot]=k[j]+pi*2;} for(int j=1,t=1;j<=tot;j++){while(t<=tot*2&&(k[t]<k[j]+pi)) t++;int l=t-j-1;int r=n-1-l-1;ans+=(1ll*l*(l-1)/2+1ll*r*(r-1)/2-1ll*l*r)*2ll;}}printf("%lld\n",ans);return 0; }

总结

以上是生活随笔为你收集整理的[XSY3381] 踢罐子（几何）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。