UVALive 7077 - Little Zu Chongzhi's Triangles(暴力)

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5089

题目大意：给n个木棒，用这n个木棒组成多个三角形，求这些三角形面积和的最大值，如果一个三角也不能组成则输出0.00

（注意：一根木棒就可以当做一条边，刚开始就错误的以为一条边可以由很多木棒共同组成而将题想复杂了）

分析：

将这n个木棒按长度从大到小排（从小到大票排是错误的，我也不知道为什么是错的--!）然后用双重循环暴力，找三角形的三

条边，利用海伦公式求三角形的面积

海伦公式：

a, b, c 分别为三角形的三条边，s为三角形的面积

p = (a + b + c)/2

s = sqrt(p(p-a)(p-b)(p-c));

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<stdlib.h>

#include<algorithm>

using namespace std;

const int N = ;

int d[N];

int cmp(const void *a, const void *b)

{

    return *(int *)b - *(int *)a;

}

bool judge(int a, int b, int c)

{

    if(a + b > c && a + c > b && b + c > a)

        return true;

    return false;

}

int main()

{

    int n, i, j, a, b, c, f;

    double s, sum, p;

    while(scanf("%d", &n), n)

    {

        sum = ;

        for(i =  ; i < n ; i++)

            scanf("%d", &d[i]);

        qsort(d, n, sizeof(d[]), cmp);

        i = ;

        while(i < n - )

        {

            f = ;

            j = i + ;

            while(j < n)

            {

                if(judge(d[i], d[j], d[j + ]))

                {

                    a = d[i];

                    b = d[j];

                    c = d[j + ];

                    p = 1.0 * (a + b + c) / ;

                    s = 1.0 * sqrt(p * (p - a) * (p - b) * (p - c));

                    sum += s;

                    i += ;

                    j = n;

                    f = ;

                }

                else

                    j++;

            }

            if(f == )

                i++;

        }

        if(sum == )

            printf("0.00\n");

        else

            printf("%.2f\n", sum);

    }

    return ;

}

巴特西

UVALive 7077 - Little Zu Chongzhi's Triangles(暴力)

最新文章

热门文章