Description

在一只大灰狼偷偷潛入Farmer Don的牛群被群牛發現后，貝西現在不得不履行著她站崗的職責。從她的守衛塔向下瞭望簡直就是一件煩透了的事情。她決定做一些開發智力的小練習，防止她睡著了。想象牧場是一個X，Y平面的網格。她將N只奶牛標記為1…N (1 <= N <= 100,000)，每只奶牛的坐標為X_i,Y_i (-100,000 <= X_i <= 100,000;-100,000 <= Y_i <= 100,000; 1 <= i <=N)。然后她腦海里想象著所有可能由奶牛構成的三角形。如果一個三角形完全包含了原點(0,0)，那么她稱這個三角形為“黃金三角形”。原點不會落在任何一對奶牛的連線上。另外，不會有奶牛在原點。給出奶牛的坐標，計算出有多少個“黃金三角形”。順便解釋一下樣例，考慮五只牛，坐標分別為(-5,0), (0,2), (11,2), (-11,-6), (11,-5)。下圖是由貝西視角所繪出的圖示。?

Input

第一行:一個整數: N 第2到第N+1行: 每行兩個整數X_i，Y_i，表示每只牛的坐標

Output

* 第一行: 一行包括一個整數，表示“黃金三角形的數量”

Sample Input

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

Sample Output

5 ———————————————————————————————— 這道題我們發現直接求黃金三角形就很難求 那么正難取反 我們可以用總的減去不符合的 那么我們考慮某一個點 那么我們從原點向這個點連一條直線? 這樣之后我們從這條線的左邊或者右邊選點 選出來的點一定是不包含原點的 我們單獨考慮一個三角形（不包含原點類的）從原點向三個端點連線 觀察發現 有一條是經過這個三角形 一條三角形在這條線的順時針方向 一條三角形在這條線的逆時針方向 所以我們單獨考慮一個方向就不會算重了 第一次接觸極角排序?我們按順時針的方向排序 從第一象限開始跑 求一下順時針方向180有多少個點 有一個結論 當前點 x1 x2 和他順時針180的一個點 x2 y2? 那么 y2*x1<y1*x2 這個可以利用差積證明 或者直接分類證明咯 然后就可以寫辣233 #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using std::sort; const int M=2e5+7,inf=0x3f3f3f3f; int read(){int ans=0,f=1,c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}return ans*f; } int n; struct pos{int x,y,wh; double k;}q[M]; bool cmp(pos a,pos b){return a.wh!=b.wh?a.wh<b.wh:a.k>b.k;} int main(){int x,y;n=read();for(int i=1;i<=n;i++){x=read(); y=read();q[i].x=x; q[i].y=y;if(x) q[i].k=1.0*y/x; else q[i].k=-inf;if(x>0&&y>=0) q[i].wh=1;else if(x>=0&&y<0) q[i].wh=2;else if(x<0&&y<=0) q[i].wh=3;else q[i].wh=4;}LL ans=1LL*n*(n-1)*(n-2)/6;sort(q+1,q+1+n,cmp);LL sum=1,ly=2;for(int i=1;i<=n;i++){sum--;while(1LL*q[ly].y*q[i].x<1LL*q[i].y*q[ly].x){ly++; sum++;if(ly>n) ly-=n;}ans=ans-sum*(sum-1)/2;}printf("%lld\n",ans);return 0; } View Code

?

轉載于:https://www.cnblogs.com/lyzuikeai/p/7598930.html

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的bzoj 1914: [Usaco2010 OPen]Triangle Counting 数三角形——极角排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。