牛客训练二：处女座的签到题（STL+精度+三角形求面积公式）

题目链接：传送门

知识点：

（1）三个点，三角形求面积公式

（2）精度问题：

double 15-16位（参考文章）

float 6-7位

long long 约20位

int 约10位

unsigned int 是int的两倍（参考文章）

（3）nth_element()函数

思路：一开始想直接暴力求面积，然后面积排序，后来有发现面积不能是0，可以重复，

然后排序求出第k大的值，结果没注意double的位数不能精确到达到18位，然后又想四舍五入，

对尾数进行了处理，还是没过。看来题解才发现最后的精度还可以分开写，get到了。

还有·就是nth_element函数的使用，排序的耗时太多，我后来选择用快排，结果还是超时了，可能是递归

太多次了，而且对全部数据排序费时，后来改用STL就行了，今后还要多看看STL。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = ;

typedef long long LL;

struct Node{

    LL x,y;

}cur[maxn];

LL vc[];

void quick_sort(int l,int r)

{

    int i=l,j=r;

    LL tmp=vc[l];

    if(l>=r) return ;

    while(i!=j)

    {

        while(i<j&&vc[j]<=tmp) j--;

        if(j>i) vc[i]=vc[j];

        while(i<j&&vc[i]>=tmp) i++;

        if(i<j) vc[j]=vc[i];

    }

    vc[i]=tmp;

    quick_sort(l,i-);

    quick_sort(i+,r);

}

int main(void)

{

    int n,k,i,j,l,t;

    double tp;

    LL cc;

    scanf("%d",&t);

    while(t--)

    {

        memset(cur,,sizeof(cur));

        memset(vc,,sizeof(vc));

        scanf("%d%d",&n,&k);

        for(i=;i<n;i++) scanf("%lld%lld",&cur[i].x,&cur[i].y);

        int pos=;

        for(i=;i<n;i++)

            for(j=i+;j<n;j++)

                for(l=j+;l<n;l++)

                {

                    cc=cur[i].x*cur[j].y+cur[j].x*cur[l].y+cur[l].x*cur[i].y-

                    (cur[i].x*cur[l].y+cur[j].x*cur[i].y+cur[l].x*cur[j].y);

                    if(cc<) cc=-cc;

                    if(cc) vc[pos++]=cc;

                }

        nth_element(vc,vc+pos-k,vc+pos);

        cc=vc[pos-k];

        if(cc%==)

        {

            printf("%lld.00\n",cc/);

        }

        else

        {

            printf("%lld.50\n",(cc-)/);

        }

    }

    return ;

}