链接：https://ac.nowcoder.com/acm/contest/327/A
来源：牛客网
题目描述
平面上有n个点，问：平面上所有三角形面积第k大的三角形的面积是多少?
输入描述:
第一行T，表示样例的个数。
对于每一组样例，第一行两个整数n和k，
接下来n行，每行两个整数x,y表示点的坐标
T<=80
3<=n<=100
-109<=x,y<=109
对于每一组样例，保证任意两点不重合，且能构成的三角形的个数不小于k
输出描述:
对于每一组样例，输出第k大三角形的面积，精确到小数点后两位（四舍五入）。
示例1
输入
1 4 3 1 1 0 0 0 1 0 -1
输出
0.50
说明
样例中一共能构成3个三角形，面积分别为0.5，0.5，和1，面积第3大的为0.5
本题的坑：
1.数据过大，不能用double存，叉积返回整数，要除2之前判断一下奇偶性，补一下小数点后缀就好了
2.叉积求三角形面积，海伦公式开根号精度不能保证
3.暴力三重循环求所有三角形，筛去同一直线上的三个点的组合。同一直线上的叉积为0。
4.不能用sort排序，复杂度为O(nlogn)，很可能爆时间，用快速排序求第k大或者调用函数nth_element，复杂度O(n)
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<set> #define ll long long #define inf 0x3f3f3f3f using namespace std; struct node { ll x; ll y; }; node p[105]; ll ans[1000005]; ll s(node p1,node p2,node p3) { ll chaji=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y); return abs(chaji); } int main() { int t; scanf("%d",&t); int n,k; while(t--) { scanf("%d%d",&n,&k);//求第k大 for(int i=1;i<=n;i++) { scanf("%lld%lld",&p[i].x,&p[i].y); } int x=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=j+1;k<=n;k++) { ll temp=s(p[i],p[j],p[k]); if(temp) ans[x++]=temp; } nth_element(ans,ans+x-k,ans+x);///排(x+1-k)小 if(ans[x-k]%2==1) printf("%lld.50 ",ans[x-k]/2); else printf("%lld.00 ",ans[x-k]/2); } return 0; } //用人话讲，排好第k+1小的元素的下标为k //用鬼话讲，从第0个排，第k个的放在下标为k的位置 //nth_element(ans,ans+k,ans+x); /*人话与鬼话 数组ans里，总元素个数为x，人话第a大和人话第b小的关系。 假设x=10，元素分别为1，2，3，4，5，6，7，8，9，10。 下标分别是0，1，2，3，4，5，6，7，8，9。 设a=3，求b等于多少？ 人话的第三大就是8，放在下标为7的空间里。 转化成人话的就是第b小，则元素8是第8小， ∴人话的大小转化是： b=x+1-a 然而写入函数找人话的第b小是计算机鬼话从0开始排，放在b-1下标里 ∴函数中间那个参数表示，人话的第b大放在下标为b-1的下标里 */