d269 - 11579 - Triangle Trouble
題目描述
題目給定一組長度，要求找出其中能構成的最大三角形面積。如果無法構成三角形，則輸出 0.00。
解題思路
首先，對給定的長度陣列進行排序。然後，從最長的邊開始，嘗試與其他兩條較短的邊組成三角形。如果滿足三角形不等式（最長邊小於其他兩邊之和），則使用海倫公式計算三角形面積，並更新最大面積。如果找不到任何可以構成三角形的三條邊，則輸出 0.00。
複雜度分析
- 時間複雜度: O(n log n) (主要來自排序)
- 空間複雜度: O(n) (用於儲存輸入陣列)
程式碼
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
int n,t;
double arr[10001];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n;
for(int i=0;i<n;++i){
cin >> arr[i];
}
double ans=0;
sort(arr,arr+n);
for(int i=n-1;i>=2;--i){
if(arr[i]<arr[i-1]+arr[i-2]){
double s=(arr[i]+arr[i-1]+arr[i-2])/2.00;
ans=max(ans,sqrt(s*(s-arr[i])*(s-arr[i-1])*(s-arr[i-2])));
}
}
cout << fixed << setprecision(2) << ans << '\n';
}
}