hdu 5135 Little Zu Chongzhi's Triangles（计算几何：三角形面积）

本文主要是介绍hdu 5135 Little Zu Chongzhi's Triangles（计算几何：三角形面积），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出多条木棍，问你用这些木棍所能组成的多个三角形面积最大和是多少

贪心做，所以先排序，但是遍历的过程中不能从前向后遍历

因为可能会存在4条边取后三条边是最优的类似情况

正解是从后向前遍历，用海伦公式求解

代码如下：

/* ***********************************************Author        :yinhuaEmail         :yinwoods@163.comFile Name     :b.cppCreated Time  :2014年12月03日 星期三 12时10分03秒************************************************ */#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 110
#define LL long long
using namespace std;double a[MAXN];bool judge(int i) {if(a[i] < a[i-1]+a[i-2])return true;return false;
}double area(int i) {double b = a[i];double c = a[i-1];double d = a[i-2];double p = (b+c+d)/2.0;return sqrt(1.0*p*(p-d)*(p-b)*(p-c));
}int main() {int n;while(~scanf("%d", &n) && n) {for(int i=0; i<n; ++i) {scanf("%lf", &a[i]);}double ans = 0.0;sort(a, a+n);for(int i=n-1; i>1; ) {if(judge(i)) {ans += area(i);i -= 3;}else --i;}printf("%.2lf\n", ans);}return 0;
}

这篇关于hdu 5135 Little Zu Chongzhi's Triangles（计算几何：三角形面积）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---