https://ac.nowcoder.com/acm/contest/327/A

C++版本一

std

題解：簡單數學，排序

由于題目條件，x，y坐標的絕對值均在1e9以下，面積可能會到達1e18，所以無法用double儲存。三角形的面積等于相鄰兩邊叉積的一半，所以三角形面積的兩倍一定是整數，我們可以用long long來儲存，最后特判輸出”.00”或”.50”。對于找第k大，時間復雜讀為O(n)，可以利用快排的思想或者利用nth_element。

#include <bits/stdc++.h> using namespace std; #define ll long long int t,n,k; struct point {ll x,y; } a[105];int main() {scanf("%d",&t);while (t--){scanf("%d%d",&n,&k);for (int i=1; i<=n; i++){scanf("%lld%lld",&a[i].x,&a[i].y);}vector<ll> v;for (int i=1; i<=n; i++){for (int j=i+1; j<=n; j++){for (int w=j+1; w<=n; w++){ll area=abs((a[j].x-a[i].x)*(a[w].y-a[i].y)-(a[w].x-a[i].x)*(a[j].y-a[i].y));v.push_back(area);}}}nth_element(v.begin(),v.begin()+n*(n-1)*(n-2)/6-k,v.end());ll ans=v[n*(n-1)*(n-2)/6-k];if (ans%2==0) printf("%lld.00\n",ans/2);else printf("%lld.50\n",ans/2);}return 0; }

?

總結

以上是生活随笔為你收集整理的处女座的签到题的全部內容，希望文章能夠幫你解決所遇到的問題。

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