题目链接 :https://ac.nowcoder.com/acm/contest/327/A?&headNav=acm
题目大意:
平面上有n个点,问:平面上所有三角形面积第k大的三角形的面积是多少?

输入描述:
第一行T,表示样例的个数。
对于每一组样例,第一行两个整数n和k,
接下来n行,每行两个整数x,y表示点的坐标
T<=80
3<=n<=100
-10^ 9<=x,y<=10^ 9
对于每一组样例,保证任意两点不重合,且能构成的三角形的个数不小于k

输出描述:
对于每一组样例,输出第k大三角形的面积,精确到小数点后两位(四舍五入)。

思路:用double莫名的T了。赛后知道爆double用long long。我竟然以为double和long long的数据范围相同。

double(双精度浮点数)使用 64 位(8字节) 来储存一个浮点数。 它可以表示十进制的15或16位有效数字
long long: 9*10^18

思路:,x,y坐标的绝对值均在1e9以下,面积可能会到达 1e18,所以无法用double储存。三角形的面积等于相邻两边叉积的一半, 所以三角形面积的两倍一定是整数,我们可以用long long来储存,最后 特判输出”.00”或”.50”。 对于找第k大,时间复杂读为O(n),可以利用快排的思想或者利用 nth_element。

nth_element(s,s+n-k,s+n);//第k大的元素在s[n-k]
nth_element(s,s+k-1,s+ans,greater<ll>());//第k大的元素在s[k-1],因为第0大为最大的元素




第16种求法:

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct
{
    ll x, y;
}e[105];

ll s[1000005];

ll S(ll i, ll j, ll k)
{
    ll x1=e[i].x, x2=e[j].x, x3=e[k].x;
    ll y1=e[i].y, y2=e[j].y, y3=e[k].y;

    return abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n, k, ans=0;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
        {
            scanf("%lld%lld",&e[i].x, &e[i].y);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    s[ans++]=S(i, j, k);
                }
            }
        }
        nth_element(s,s+ans-k,s+ans);
        if(s[ans-k]%2==1)
        {
            printf("%lld.50\n",s[ans-k]/2);
        }
        else
        {
            printf("%lld.00\n",s[ans-k]/2);
        }

    }

    return 0;
}