https://ac.nowcoder.com/acm/contest/327/A
C++版本一
std
题解:简单数学,排序
由于题目条件,x,y坐标的绝对值均在1e9以下,面积可能会到达1e18,所以无法用double储存。三角形的面积等于相邻两边叉积的一半,所以三角形面积的两倍一定是整数,我们可以用long long来储存,最后特判输出”.00”或”.50”。对于找第k大,时间复杂读为O(n),可以利用快排的思想或者利用nth_element。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int t,n,k;
struct point
{
ll x,y;
} a[105];
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&k);
for (int i=1; i<=n; i++)
{
scanf("%lld%lld",&a[i].x,&a[i].y);
}
vector<ll> v;
for (int i=1; i<=n; i++)
{
for (int j=i+1; j<=n; j++)
{
for (int w=j+1; w<=n; w++)
{
ll area=abs((a[j].x-a[i].x)*(a[w].y-a[i].y)-(a[w].x-a[i].x)*(a[j].y-a[i].y));
v.push_back(area);
}
}
}
nth_element(v.begin(),v.begin()+n*(n-1)*(n-2)/6-k,v.end());
ll ans=v[n*(n-1)*(n-2)/6-k];
if (ans%2==0) printf("%lld.00\n",ans/2);
else printf("%lld.50\n",ans/2);
}
return 0;
}