计算三角形面积

时间：2023-01-09 10:06:12

参考：
根据平面内三点坐标，求面积

计算三角形面积

1：已知直角坐标系3点p(a,b),m(c,d),n(e,f) 求三角形pmn面积

两倍三角形面积是整型，

代码模板：

ll solve(ll a,ll b,ll c,ll d,ll e,ll f)//计算两倍三角形面积
{
	return abs(a*d+b*e+c*f-a*f-b*c-d*e);
}

此写法可以不爆long long，之后再除以2即可

2，若是由三条边求面积，则海伦公式：

　　　　　　　　　　　　　　　　计算三角形面积

模板为：

double hailun(double a,double b,double c)
{//保证尽量不爆long long
	double s;
    double pp=(a+b+c)/2.0;
    double s1=sqrt(fabs(pp));
    double s2=sqrt(fabs(pp-a));
    double s3=sqrt(fabs(pp-b));
    double s4=sqrt(fabs(pp-c));
    s=s1*s2*s3*s4;
    return s;
}

 3，判断三点一线

bool judge(node a,node b,node c)
{
	return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x)!=0;
}

　　

参考例题：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

WA点：1,此题用海伦公式会爆double 和 long long
　　　 2,寻找第K大，若不用STL（nth_element），直接sort大法，会超时....

AC代码：

计算三角形面积计算三角形面积
 1 #include <bits/stdc++.h>
 2   
 3 using namespace std;
 4 #define sc(a) scanf("%d",&a)
 5 #define sc2(a,b) scanf("%d%d",&a,&b)
 6 #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
 7 #define scl(a) scanf("%lld",&a)
 8 #define scl2(a,b) scanf("%lld%lld",&a,&b)
 9 #define scl3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
10 #define l_b lower_bound
11 #define u_b upper_bound
12   
13 #define min_2(a,b) a<b?a:b
14 #define min_3(a,b,c) min_2(min_2(a,b),c)
15 #define max_2(a,b) a>b?a:b
16 #define max_3(a,b,c) max_2(max_2(a,b),c)
17 #define ll long long
18 #define rint register int
19 #define mem0(x) memset(x, 0, sizeof(x))
20 #define mem1(x) memset(x, -1, sizeof(x))
21 #define lowbit(x)  x&-x
22 /**inline int read()///神奇的读优
23 {
24     int x=0,f=1;char c=getchar();
25     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
26     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
27     return x*f;
28 }*/
29 ///2147483647 -2147483648
30 ///9223372036854775807 -9223372036854775808
31 //freopen("input.txt", "r", stdin);
32 const double PI=acos(-1.0);
33 const int inf = 0x3f3f3f3f;
34 const ll inff = 0x3f3f3f3f3f3f3f3f;
35 const int mod = 1e9+7;
36 const int maxn= 1e8+5;
37   
38 //map<ll,ll>mp;
39 //set<ll>st;
40 //stack<>st;
41 //queue<>Q;
42 /***********************************************/
43 vector<ll>V;
44 ll x[200+3],y[200+3];
45 
46  
47 ll solve(ll a,ll b,ll c,ll d,ll e,ll f)
48 {
49     return abs(a*d+b*e+c*f-a*f-b*c-d*e);
50 }
51 
52 int main()
53 {
54     int T;
55     cin>>T;
56     while(T--)
57     {
58         V.clear();
59         int n,k;
60         sc2(n,k);
61          
62         for(int i=1;i<=n;i++){
63             scanf("%lld%lld",&x[i],&y[i]);
64         }
65          
66         for(int i=1;i<=n-2;i++)
67         {
68             for(int j=i+1;j<=n-1;j++){
69                 for(int p=j+1;p<=n;p++){
70                     ll ans=solve(x[i],y[i],x[j],y[j],x[p],y[p]);
71                     if(ans) V.push_back(ans);
72                 }
73             }
74         }
75         int nn=V.size();
76         nth_element(V.begin(),V.begin()+nn-k,V.end());
77         if(V[nn-k]%2)
78         printf("%lld.50\n",V[nn-k]/2);
79         else
80         printf("%lld.00\n",V[nn-k]/2);
81     }
82     return 0;
83 }
View Code

参考STL->>>>>>>自家博客：STL之nth_element__寻找第n大的元素

标签：

相关文章