链接: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;
}