处女座的沙比签到题 三角形面积公式

角形面积公式"/>

处女座的沙比签到题 三角形面积公式

题目

参考代码

思路：

　　一个三角形的面积=1/2 absinC，即1/2| a x b | （a b为向量），利用矩阵，算得S=1/2 * abs（x1*y2 - x2*y1） （x1,y1,是向量a的横纵坐标。x2,y2是向量b的横纵坐标）。  证明

　　由此，三角形面积的两倍 一定是个整数，所以三角形面积的小数点后面要么 .00，要么 .50 。用double和海伦公式存入数组 sort 排序会超时，应该是两两比较的计算次数过多，因为是double。

　　关于函数 nth_element()

　　优先队列 默认从小到大自动排序。

　　priority_queue<int, vector<int>,greater<int> >q; //从大到小

#include<iostream>
#include<cstdio>
#include <cctype>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a))
#define se second
#define fi first
const ll mod=1e9+7;
const int INF= 0x3f3f3f3f;
const int N=1e6+5;int n,m;
ll x[105],y[105];int main()
{int T; cin>>T;ll x1,x2,x3,y1,y2,y3;ll sum;while(T--){priority_queue<ll,vector<ll>,greater<ll> >q;cin>>n>>m;for(int i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);for(int i=1;i<=n-2;i++){for(int j=i+1;j<=n-1;j++){for(int k=j+1;k<=n;k++){x1=x[i]-x[k];x2=x[j]-x[k];y1=y[i]-y[k];y2=y[j]-y[k];sum=abs(x1*y2-x2*y1);if(sum==0) continue;if(q.size()<m)q.push(sum);else if(q.top()<sum){q.pop();q.push(sum);}}}}ll ans=q.top();if(ans%2==0)printf("%lld.00\n",ans/2);elseprintf("%lld.50\n",ans/2);}}

转载于:.html