找第k大&求三角形面积

牛客寒训2

题目描述

平面上有n个点，问：平面上所有三角形面积第k大的三角形的面积是多少?

输入描述:

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

输出描述:

对于每一组样例，输出第k大三角形的面积，精确到小数点后两位（四舍五入）。

示例输入

1
4 3
1 1
0 0
0 1
0 -1

示例输出

0.50

说明

样例中一共能构成3个三角形，面积分别为0.5，0.5，和1，面积第3大的为0.5

思路

1. 求三角形面积 ——三角形的面积等于相邻两边叉积的一半
   点积：
   叉积：

2. 精度问题 double的有效数字是15-16位，这一题的最大可达1e18，再加上保留的两位小数，所以共有19+2位，double无法存储这么多的有效数字，会使16位后的数字都变成0；
   因此用long long存储2*S，最后输出的时候判断奇偶再加上0.50或0.00
3. 求一个无序序列中第k大的数

• nth_element函数，nth_element(start, start+n, end) 可以使第n小元素处于第n位置（从0开始,其位置是下标为 n的元素）
• 快速排序，若下标从0开始，可以找出第n-k小的数，则表示第k大的数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
//
//找第k大的数可以用快排或者，
ll s[1000002];
ll x[105], y[105];
 
int Partition (int low, int high)
{
    ll temp = s[low]; //哨兵
    while (low < high)
    {
        while (low < high && s[high] >= temp)
            high--;
        s[low] = s[high];
        while (low < high && s[low] <= temp)
            low++;
        s[high] = s[low];
    }
    s[low] = temp;
    return low;
}
 
void find_k(int k,int low,int high)
{
    int temp;
    temp = Partition(low, high);
    if(temp == k-1)
    {
        if(s[temp]&1)
            printf("%lld.50\n", s[temp]/2);
        else
            printf("%lld.00\n", s[temp]/2);
    }
    else if(temp > k-1)
        find_k(k, low, temp-1);
    else
        find_k(k, temp+1, high);
}
 
int main()
{
    int n, k, t;
    ll S;
    while(~scanf("%d", &t))
    {
        memset(s, 0, sizeof(s));
        while(t--){
                scanf("%d%d", &n, &k);
            for(int i=0; i<n; ++i)
                scanf("%lld%lld", &x[i], &y[i]);
            int q = 0;
            for(int i = 0; i<n-2; ++i)
                for(int j=i+1; j<n-1; ++j)
                    for(int p=j+1; p<n; ++p){
                        //S = x[i]*y[j]+x[j]*y[p]+x[p]*y[i]-x[i]*y[p]-x[j]*y[i]-x[p]*y[j];
                        S = (x[j]-x[i])*(y[p]-y[i]) - (x[p]-x[i])*(y[j]-y[i]);
                        S = S < 0 ? (-S) : S;
                        //if(S != 0)
                        s[q++] = S;
                    }
            nth_element(s, s+n*(n-1)*(n-2)/6-k, s+n*(n-1)*(n-2)/6); //C(3,n)为总数，
            ll ans = s[n*(n-1)*(n-2)/6-k];
            /*if(ans&1)
                cout << ans/2 << ".50" << endl;
            else
                cout << ans/2 << ".00" << endl;
            */
            find_k(q-k+1, 0, q-1);   //快排
        }
    }
    return 0;
}