邢台市建设工程质量监督网站,做关键词排名卖网站,郑州网站制作电话,sem是什么职业处女座的签到题 链接#xff1a;https://ac.nowcoder.com/acm/contest/327/A 题目描述 平面上有n个点#xff0c;问#xff1a;平面上所有三角形面积第k大的三角形的面积是多少?输入描述: 第一行T#xff0c;表示样例的个数。对于每一组样例#xff0c;第一行两个整数n和…处女座的签到题 链接https://ac.nowcoder.com/acm/contest/327/A 题目描述 平面上有n个点问平面上所有三角形面积第k大的三角形的面积是多少? 输入描述: 第一行T表示样例的个数。对于每一组样例第一行两个整数n和k接下来n行每行两个整数x,y表示点的坐标T80 3n100 -109x,y109 对于每一组样例保证任意两点不重合且能构成的三角形的个数不小于k 输出描述: 对于每一组样例输出第k大三角形的面积精确到小数点后两位四舍五入。 示例1 输入 1
4 3
1 1
0 0
0 1
0 -1输出 0.50说明 样例中一共能构成3个三角形面积分别为0.50.5和1面积第3大的为0.5题解这个题很迷 用海伦公式不过用sort排序超时。也算是新学了一招吧 还有数据太大会超double 故用long double。计算几何中三角形四边形计算公式https://blog.csdn.net/enjoying_science/article/details/41170505 1 #includeiostream2 #includecstdio3 #includecstring4 #includecmath5 #includealgorithm6 using namespace std;7 const int maxn1e610;8 int n,k;9 int casen;
10 long double e[maxn];
11 long double ans[maxn];
12 long double x[110],y[110];
13 int cmp(long double x,long double y)
14 {
15 return xy;
16 }
17 int main()
18 {
19 scanf(%d,casen);
20 while(casen--)
21 {
22 memset(e,0,sizeof(e));
23 memset(ans,0,sizeof(ans));
24 scanf(%d%d,n,k);
25 for(int i0;in;i)
26 {
27 cinx[i]y[i];
28 }
29 int t0;
30 for(int i0;in;i)
31 {
32 for(int ji1;jn;j)
33 {
34 for(int kj1;kn;k)
35 {
36 long double a0.5*abs(x[i]*y[j]x[j]*y[k]x[k]*y[i]-x[i]*y[k]-x[j]*y[i]-x[k]*y[j]);
37
38 e[t]a;
39 }
40 }
41 }
42 nth_element(e,ek-1,et,cmp);
43
44 printf(%.2Lf\n,e[k-1]);
45 }
46 } 转载于:https://www.cnblogs.com/1013star/p/10366770.html
