哗啦啦村的刁难(4)

发布时间: 2017年2月28日 20:00 最后更新: 2017年2月28日 20:02 时间限制: 1000ms 内存限制: 128M

描述

哗啦啦村作为喵哈哈村的对头，于是他们准备给喵哈哈村一个好看。

哗啦啦村的四长老——四先生，就提出了以下问题：

给你n条边，让你从里面选出三条边，组成一个三角形，问你这个三角形最大的面积可以为多少？

如果无论如何都不能组成三角形，输出-1。

输入

第1行：一个整数n，表示边的个数。
第2行，n个整数，表示每条边的边长。
1<=n<=100 1<=a[i]<=100

输出

输出最大面积，无解输出-1.
保留整数即可。

样例输入1 复制

4
1 5 3 4

样例输出1

6

直接暴力求解

 1 #include <iostream>
 2 #include <bits/stdc++.h>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 int n[105];
 7 
 8 int main() {
 9     int a;
10     while (cin >> a) {
11         double Max=-1;
12         memset(n,0,sizeof(n));
13         for (int i = 0; i < a; i++) {
14             cin >> n[i];
15         }
16         sort(n, n + a);
17             for (int i = 0; i < a; i++) {
18                 for (int j = i + 1; j < a; j++) {
19                     for (int k = j + 1; k < a; k++) {
20                         if(n[i]+n[j]>n[k]) {
21                             double y = (n[i] + n[j] + n[k])/2.0;
22                             double x = sqrt(y * (y - n[i]) * (y - n[j]) * (y - n[k]));
23                             if(x>Max) Max=x;
24                         }else
25                             break;
26                     }
27                 }
28             }
29         printf("%.0f
", Max);  
30     }
31     return 0;
32 }