牛客寒假算法集訓營2
https://ac.nowcoder.com/acm/contest/327/A
A.處女座的簽到題
題目描述
平面上有n個點，問：平面上所有三角形面積第k大的三角形的面積是多少?


/*

---

已知坐標求三角形的面積，最好的方法是求出相鄰兩個向量的叉積的絕對值（平行四邊形面積）然后除以2
比如由三個點A(x1,y1)，B(x2,y2),C(x3,y3)構成的三角形ABC
求它面積的公式為：
|向量AB×向量AC| / 2 = |(x2-x1)(y3-y1)-(x3-x1)(y2-y1)| / 2;
關于向量叉積求三角形面積，這里有一篇寫的十分好比較全的博客：傳送門

---

對于本題，因為要除以2，并且要求保留2位小數，叉積的絕對值要不是奇數要不就是偶數，所以可以把叉積絕對值算出來用long long數組（喜歡省內存）存起來，然后分奇數偶數討論保留的后兩位小數是什么（even : %lld.00 odd :%lld.50）~
然后要求第K大的面積，時間復雜度為O（n），可以用快排的思想（“快速選擇算法”），也可以用STL里的nth_element；

---

nth_element基本用法和sort有點像：
nth_element作用為求第n大的元素，并把它放在第n位置上，如果數組是從0開始存的數據，那么用法為nth_element(a,a+k-1,a+n,cmp);
第一個為數組首地址，第二個為第K個數的地址，第三個為末地址，最后一個是排序方式（不寫cmp，默認是升序的）
注意：nth_element()函數不過將第n大的數排好了位置，并不返回值

---

*/
AC_code:

#include <stdio.h> #include <algorithm> #define ll long long const ll N = 10e6; using namespace std; struct date {ll x;ll y; }; bool cmp(ll a,ll b) {return a > b; } long long a[N]; int main() {int t,n,k;scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);date d[n+2];for(int i = 0; i < n; i++){scanf("%lld%lld",&d[i].x,&d[i].y);}ll v = 0,w;for(int i = 0; i < n; i++){for(int j = i+1; j < n; j++){for(int k = j+1; k < n; k++){w = (d[j].x-d[i].x)*(d[k].y-d[i].y)-(d[k].x-d[i].x)*(d[j].y-d[i].y);a[v++] = w > 0 ? w : - w;}}}nth_element(a,a+k-1,a+v,cmp);if(a[k-1]%2==0)printf("%lld.00\n",a[k-1]/2);elseprintf("%lld.50\n",a[k-1]/2);}return 0; }

總結

以上是生活随笔為你收集整理的利用向量叉积求三角形的面积（+STL：nth_element求第K大的数）的全部內容，希望文章能夠幫你解決所遇到的問題。

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