牛客寒假算法基础集训营2 A处女座的签到题

处女座的签到题

链接：https://ac.nowcoder.com/acm/contest/327/A

题目描述

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

输入描述:

第一行T，表示样例的个数。
对于每一组样例，第一行两个整数n和k，
接下来n行，每行两个整数x,y表示点的坐标
T<=80 3<=n<=100 -10⁹<=x,y<=10⁹ 对于每一组样例，保证任意两点不重合，且能构成的三角形的个数不小于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
题解：
这个题很迷 用海伦公式不过，用sort排序超时。也算是新学了一招吧 还有数据太大会超double 故用long double。
计算几何中三角形四边形计算公式：https://blog.csdn.net/enjoying_science/article/details/41170505

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int maxn=1e6+10; 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 x>y; 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 i=0;i<n;i++) 26 { 27 cin>>x[i]>>y[i]; 28 } 29 int t=0; 30 for(int i=0;i<n;i++) 31 { 32 for(int j=i+1;j<n;j++) 33 { 34 for(int k=j+1;k<n;k++) 35 { 36 long double a=0.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,e+k-1,e+t,cmp); 43 44 printf("%.2Lf\n",e[k-1]); 45 } 46 }

 

转载于:https://www.cnblogs.com/1013star/p/10366770.html

总结

以上是生活随笔为你收集整理的牛客寒假算法基础集训营2 A处女座的签到题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。