三角形问题II

布满荆棘的人生 2022-08-07 08:39 165阅读 0赞

Submit [Status][] [Practice][] [ FZU 1888][FZU 1888]

Description

给定平面上的N 个点的坐标，现在你的任务是统计任意3个点构成的三角形的面积和的值。

Input

有多组数据

数据的第一行包含一个正整数T表示数据组数(1 <= T <= 100) 接下来T组数据。

对于每组数据，

第一行包含一个正整数N，代表平面上点的个数 。(1<= N <= 50,)

接下来N行，每行包含2个实数Xi, Yi，代表第i个点的坐标 (0.00 <= Xi,Yi <= 100.00小数点后至多2位)

数据不保证不会出现坐标相同的点。

Output

对于每组数据，首先输出”Case d: “，d为数据编号(从1开始)。只输出一个实数，表示面积和的值。(输出小数点后1位)

Sample Input

1  
3  
0 0  
1 1  
1 0

Sample Output

Case 1: 0.5

提示：模拟计算方式；

代码：

\#include <stdio.h>  
\#include<math.h>  
double fac(double e,double r,double t)  
\{  
    double q=(e+r+t)/2,w;  
    w=sqrt(q\*(q-e)\*(q-r)\*(q-t));  
    return w;  
\}  
int main()  
\{  
    int b,c,d,n,q,j,i=0;  
    double e,r,t,w;  
    double a\[50\],y\[50\];  
    scanf("%d",&n);  
    while(n--)  
    \{  
        w=0;//表示是三角形的面积之和  
        scanf("%d",&q);  
        for(j=0;j<q;j++)  
            scanf("%lf %lf",&a\[j\],&y\[j\]);//录入每个点  
        for(d=0;d<=q-3;d++)//控制第一点的循环  
        \{  
            for(b=d+1;b<=q-2;b++)//控制第二点的循环  
            \{  
                for(c=b+1;c<=q-1;c++)//控制第三点的循环  
                \{  
                    e=sqrt((a\[d\]-a\[b\])\*(a\[d\]-a\[b\])+(y\[d\]-y\[b\])\*(y\[d\]-y\[b\]));  
                    r=sqrt((a\[d\]-a\[c\])\*(a\[d\]-a\[c\])+(y\[d\]-y\[c\])\*(y\[d\]-y\[c\]));  
                    t=sqrt((a\[c\]-a\[b\])\*(a\[c\]-a\[b\])+(y\[c\]-y\[b\])\*(y\[c\]-y\[b\]));//算任意三个点的组成三角形的边长  
                    if((e+r>t)&&(e+t>r)&&(r+t>e))//判断是否能构成三角形  
                    w=w+fac(e,r,t);//求三角行的面积海伦公式  
                \}  
            \}  
        \}  
            printf("Case %d: %.1lf\\n",i+1,w);  
            i++;  
    \}  
    return 0;  
\}

Hint

请使用double代替float以避免精度问题

[Status]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=72472#status//H/0
[Practice]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=137346
[FZU 1888]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=137346