ZJ d269: 11579 - Triangle Trouble
題目連結
題目敘述
有一個三角形工廠有一個很大的問題。給你一些邊的邊長，想辦法找出用這些邊長圍出最大的三角形。
根據海龍公式，三角形面積：
可以利用貪婪法，將所有邊長由大到小進行排序，每一次拿最大的三個邊長進行枚舉，即可算出最大的三角形面積。不難理解，當換上一個比較大的邊，算出來的s也會比較大，跟邊相減的值也會比較大，總面積自然較大（好啦，這是非常不嚴謹的證明XD）
在想題過程中，我有思考到，如果周長一樣的情況下，到底何種面積的三角形面積會比較大？答案是正三角形！
三角形周長固定下面積的比較
根據海龍公式：
想要比較在周長固定下三角形的面積，可以用算幾不等式比較，因為 $s$ 是定值，所以可以列出以下式子：
等好成立時，$a=b=c$。因為$s = \frac{a+b+c}{2}$，因此：
得到海龍公式
以下是使用貪婪法的AC Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <bits/stdc++.h>
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define pdd pair<double,double>
#define ll long long
#define ld double
#define N 100001
#define all(x) x.begin(),x.end()
#define eps 1e-9
#define x first
#define y second
using namespace std;
int t,n;
vector<ld> p;
ld area(ld a ,ld b, ld c){
if(a > b + c)return -1;
ld p = (a+b+c)/2;
return p*(p-a)*(p-b)*(p-c);
}
signed main(){
Orz;
cin>>t;
while(t--){
cin>>n;
p.assign(n,0);
rep(i,0,n-1)cin>>p[i];
sort(all(p),greater<>());
ld ans = 0;
rep(i,0,n-3)
ans = max(ans,area(p[i],p[i+1],p[i+2]));
cout<<fixed<<setprecision(2);
cout<<sqrt(ans)<<endl;
}
}
|