XSY3381

點被選為點對之一的貢獻我們單獨計算（這部分貢獻的總和為$4n(n?1)(n?2)$）。接下來只討論剩余部分的貢獻。

先把任意三個點構(gòu)成的六種選擇方案合并，發(fā)現(xiàn)在外接圓周和弦之間的點每個有2的貢獻，在外接圓上的點每個有1的貢獻。

然后考慮任意四個點$A,B,C,D$的貢獻。
發(fā)現(xiàn)當四個點構(gòu)成凸四邊形$ABCD$時，
若$\angle A+\angle D=180°$：
$A,B,C,D$四點共圓，即其中一個點在另外三個點構(gòu)成的三角形的外接圓上，因此$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°$。類似上種情況。

當四個點構(gòu)成凹四邊形時，易證四個點產(chǎn)生的貢獻為0。

因此問題轉(zhuǎn)化為統(tǒng)計凸四邊形個數(shù)。

給出四個構(gòu)成凸四邊形的點，任選兩個點連邊，有4種情況剩下兩個點在連邊同側(cè)，2種情況剩下兩個點在連邊異側(cè)。

給出四個構(gòu)成凹四邊形的點，任選兩個點連邊，有3種情況剩下兩個點在連邊同側(cè)，3種情況剩下兩個點在連邊異側(cè)。

因此設(shè)整張圖中有$a$個凸四邊形，$b$個凹四邊形，
$$X=\sum _{i<j}i,j連邊，再無序地選兩個點，選的點在連邊同側(cè)的方案數(shù)$$
$$Y=\sum _{i<j}i,j連邊，再無序地選兩個點，選的點在連邊異側(cè)的方案數(shù)$$

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

解得：

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

具體實現(xiàn)上，
對于每個點，把剩下的所有點按照和它的連線的斜率排序，求斜率可以用$atan2l$函數(shù)（加上$l$避免爆精度）

然后，考慮兩個點的連線，設(shè)連線兩側(cè)的點數(shù)分別是$L$和$R$（注意這里要判斷，不能構(gòu)成了一個箭頭的形狀）

選兩個點在連線同側(cè)的有$\frac{(L?1)L+(R?1)R}{2}$種情況，選兩個點在連線異側(cè)的有$L\times R$種情況。

時間復(fù)雜度$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; }

總結(jié)

以上是生活随笔為你收集整理的[XSY3381] 踢罐子（几何）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。