3524 - F. 火柴三角形
丁丁平时希望收集火柴，今天他突然心血来潮用这些火柴拼起了三角形，他想找出其中三根火柴拼出一个面积最大的三角形，请你帮帮他。
题目输入
输入包含多组测试数据不超过50组，每组数组第一行是一个正数N (<100)，接着是N个正数，表示N根火柴的长度，每根长度小于100000。
题目输出
对于每组输入，输出最大的三角形的面积，保持2位小数，如果那组火柴拼不出一个三角形，则输出no triangle。
输入/输出样例
题目输入
3 1 9 10 4 1 1 1 1 3 3 4 5
题目输出
no triangle 0.43 6.00
提示
除了利用海伦公式，还可以耐性先从三条边求出其中一个角，然后就可以计算面积。
C语言解答
#include <stdio.h> #include <math.h> double getArea(int a, int b, int c) { int temp = a + b + c; double sum = temp; temp = a + b - c; if(temp <= 0) return 0; sum *= temp; temp = a + c - b; if(temp <= 0) return 0; sum *= temp; temp = b + c - a; if(temp <= 0) return 0; sum *= temp; return sqrt(sum) / 4; } int main() { int N; int *length; int i, j, z; double areaMax, temp; while(scanf("%d", &N) == 1) { areaMax = 0; length = (int*)malloc(sizeof(int) * N); for(i = 0; i < N; i++) scanf("%d", length+i); for(i = 0; i < N - 2; i++) { for(j = i + 1; j < N - 1; j++) { for(z = j + 1; z < N; z++) { temp = getArea(length[i], length[j], length[z]); if(temp > areaMax) areaMax = temp; } } } if(areaMax == 0) printf("no triangle\n"); else printf("%.2f\n", areaMax); } return 0; }
C++解答
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; double CalcArea(int a, int b, int c) { double area = -1; if ((a + b > c) && (a + c > b) && (b + c > a)) { double p = (a + b + c) / 2.0; area = p * (p - a) * (p - b)*(p - c); area = sqrt(area); } return area; } double Process(vector<int> &v) { if (v.size() <= 2) return -1; int a, b, c; double maxArea = -1, area; for (int i = 0; i < v.size() - 2; i++) { a = v[i]; for (int j = i + 1; j < v.size() - 1; j++) { b = v[j]; for (int k = j + 1; k < v.size(); k++) { c = v[k]; area = CalcArea(a, b, c); if (area == -1) break; if (area > maxArea) maxArea = area; } } } return maxArea; } int main() { int n, a; double area; vector<int> v; while (cin >> n) { v.clear(); v.reserve(n); while (n--) { cin >> a; v.push_back(a); sort(v.begin(), v.end());//按边长排序 } area = Process(v); if (area == -1) //cout << "no triangle" << endl; printf("no triangle\n"); else printf("%.2lf\n", area); //cout <<setiosflags(ios::fixed)<<setprecision(2) << area << endl; } return 0; }
提示
除了利用海伦公式，还可以耐性先从三条边求出其中一个角，然后就可以计算面积。