链接:https://ac.nowcoder.com/acm/contest/327/A
来源:牛客网
 

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

平面上有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

题意:中文题不解释:
题解:
知道三点求三角形面积: 

设A(x1,y1),B(x2,y2),C(x3,y3)      S=(1/2)*(x1y2+x2y3+x3y1-x1y3-x2y1-x3y2) 注意:写代码的时候要用0.5不要用1/2,你懂得~~嘻嘻~~~

这个题要注意,C++要用STL里面的  nth_element(没见过的读者自行查阅),用sort、优先队列 会超时~~还要注意数据范围,用double不行,要用long double,其它注意请看代码。

上代码:

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long double ld;//注意数据范围
const int MAX = 1e6;//三角形个数要注意,这里我习惯直接就开1e6不管点还是三角形个数,读者可自行分配
struct hh{
    ld x,y;
}a[MAX];
ld mm[MAX];
bool cmp(ld a,ld b){
    return a>b;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        int n,k,cnt;
        cin >> n >> k;
        cnt=0;
        for (int i = 0; i < n;i++){
            cin >> a[i].x >> a[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++){
                    mm[cnt++]=0.5*abs(a[i].x*a[j].y+a[j].x*a[k].y+a[k].x*a[i].y-a[i].x*a[k].y-a[j].x*a[i].y-a[k].x*a[j].y);//求面积公式
                }
            }
        }
        nth_element(mm,mm+k-1,mm+cnt,cmp);//找到第几大三角形
        printf("%.2Lf\n",mm[k-1]);//long double输出要用%Lf 大写L
    }
    return 0;
}