#1245 : 王胖浩與三角形

時間限制:1000ms 單點時限:1000ms 內存限制:256MB

描述

王胖浩有一個三角形，三邊長為a,b,c。他有特殊的能力，能增加三條邊的邊長，增加的總長度不能超過l。

他想通過合理地使用他的特殊能力，使得三角形的面積最大。

輸入

第一行一個整數T，表示測試數據個數。

以下T行，每行一個四個整數a,b,c,l。

數據范圍:

1<=T<=104, 1<=a,b,c<=106, 0<=l<=106

輸出

輸出T行，每行一個實數，表示三角形的面積。要求相對誤差不能超過10-9。

樣例輸入

1 2 3 3 3

樣例輸出

5.8216152143

已知三角形的三個邊長a,b,c,其面積是sqrt((a+b+c)*(a+b-c)*(a+c-b)*(b+c-a))/4。

考慮面積公式sqrt((a+b+c)(a+b-c)(b+c-a)(a+c-b))/4，如果固定了a和b+c，那么b和c越接近越好。

所以將三條邊排序，首先增加第一條邊到和第二條邊一樣長，然后一起增加前兩條邊到和第三條邊一樣長，然后三條邊一起增加。

代碼：

#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #pragma warning(disable:4996) using namespace std;double a[5], res, ll;int main() {//freopen("i.txt","r",stdin);//freopen("o.txt","w",stdout);int test;scanf("%d", &test);while (test--){cin >> a[0] >> a[1] >> a[2] >> ll;sort(a, a + 3);if (ll <= a[1] - a[0]){a[0] = a[0] + ll;}else{ll = ll - (a[1] - a[0]);a[0] = a[1];if (ll/2 <= a[2] - a[1]){a[1] = a[1] + ll / 2;a[0] = a[0] + ll / 2;}else{ll = ll - 2 * (a[2] - a[1]);a[1] = a[2];a[0] = a[2];a[0] = a[0] + ll / 3;a[1] = a[1] + ll / 3;a[2] = a[2] + ll / 3;}}res = sqrt((a[0] + a[1] + a[2])*(a[0] + a[1] - a[2])*(a[1] + a[2] - a[0])*(a[0] + a[2] - a[1])) / 4;printf("%.10lf\n", res);}//system("pause");return 0; }

總結

以上是生活随笔為你收集整理的HihoCoder 1245：王胖浩与三角形 三角形边长与面积的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。