Description

在一只大灰狼偷偷潛入Farmer Don的牛群被群牛發(fā)現(xiàn)后，貝西現(xiàn)在不得不履行著她站崗的職責(zé)。從她的守衛(wèi)塔向下瞭望簡直就是一件煩透了的事情。她決定做一些開發(fā)智力的小練習(xí)，防止她睡著了。

想象牧場是一個X，Y平面的網(wǎng)格。她將N只奶牛標(biāo)記為1…N (1 <= N <= 100,000)，每只奶牛的坐標(biāo)為X_i,Y_i (-100,000 <= X_i <= 100,000;-100,000 <= Y_i <= 100,000; 1 <= i <=N)。然后她腦海里想象著所有可能由奶牛構(gòu)成的三角形。如果一個三角形完全包含了原點(0,0)，那么她稱這個三角形為“黃金三角形”。原點不會落在任何一對奶牛的連線上。另外，不會有奶牛在原點。

給出奶牛的坐標(biāo)，計算出有多少個“黃金三角形”。

Input

• 第一行：一個整數(shù)N

• 第2到第N+1行：每行兩個整數(shù)X_i，Y_i，表示每只牛的坐標(biāo)

Output

• 第一行: 一行包括一個整數(shù)，表示“黃金三角形的數(shù)量”

Sample Input

5
-5 0
0 2
11 2
-11 -6
11 -5

Sample Output

5

Hint

考慮五只牛，坐標(biāo)分別為(-5,0), (0,2), (11,2), (-11,-6), (11,-5)。

下圖是由貝西視角所繪出的圖示。

............|........................*..........*.............|............-------*----+------------............|........................|........................|........................|........................|..........*..*..........|........................|............

Solution

• 正難則反，總組合數(shù)為 C3n ，只要求出不過原點的三角形個數(shù)即可。

• 現(xiàn)將每個點進行極角排序（以原點為頂點、兩邊分別為 x的正半軸 和 原點與這個點的連邊）

• 按角從小到大枚舉，統(tǒng)計連續(xù)的一段，使得組成的三角形不包含原點，則該段可以兩兩匹配。

• 判斷其是否包含原點，只需要判斷兩向量的叉積是否大于0即可（大于0則不包含）。

• 時間復(fù)雜度為 O(N?log?N) 。

Code

#include<cstdio> #include<algorithm> #include<cctype> #include<complex> using namespace std; typedef long long LL; typedef complex<LL> point; const int N=1e5+2; point a[N<<1]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool upper(point x) {return x.imag()>0 || !x.imag() && x.real()>0; } inline LL cross(point x,point y) {return x.real()*y.imag()-x.imag()*y.real(); } inline bool cmp(point x,point y) {bool xx=upper(x),yy=upper(y);if(xx && !yy) return true;if(!xx && yy) return false;return cross(x,y)>0; } int main() {int n=read();for(int i=1;i<=n;i++) a[i].real()=read(),a[i].imag()=read();sort(a+1,a+1+n,cmp);LL ans=n*1LL*(n-1)*(n-2)/6;for(int i=1;i<=n;i++) a[i+n]=a[i];for(int i=1,j=1;i<=n;i++){while(j<i+n-1 && cross(a[i],a[j+1])>0) j++;ans-=(j-i)*1LL*(j-i-1)/2;}printf("%lld",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 3129. 【WinterCamp 2013】数三角形的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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