处女座的签到题

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;
}