2015
09-17

# The Happy Triangles

Alice has a toy, which was made up by two parts. The first part is a frame consisting of one horizontal stick and two vertical sticks. The distance between the two vertical sticks is R. And the horizontal stick is long enough. The second part of her toy is N triangles. These triangles can be fastened on the frame with one of their edges on the horizontal stick. Once they are fastened, they can slide along the horizontal stick. And magically, they can overlap each other. (See pic 1)
Now, Alice wants to maximize the total area covered by these triangles between the two vertical sticks.
Note ：
1. The triangles DON’t have to be totally between the two vertical sticks. But the area out of the two sticks should not be taken into consideration.
2. These triangles are either acute triangle or right triangle.

There are several cases. The first line of the input is a single integer T. (T<=100)
For each case, the first line contains two integers N ,R. (N<=1000,R<=100000)
The next N lines, each line contains three integer a,b,c , which stand for the lengths of three edges of the i-th triangle.
(0<a<=b<=c<100000,a2+b2>=c2).

There are several cases. The first line of the input is a single integer T. (T<=100)
For each case, the first line contains two integers N ,R. (N<=1000,R<=100000)
The next N lines, each line contains three integer a,b,c , which stand for the lengths of three edges of the i-th triangle.
(0<a<=b<=c<100000,a2+b2>=c2).

2
1 5
3 4 5
2 4
3 4 5
3 4 5

Case #1: 6.000
Case #2: 10.667

1. 每个三角形都应该把最短边与底线重合。

2. 存在重叠时，所有三角形之间的交点以及三角形与左右两条竖线的交点应该在同一水平线上。

（证明的话，我就不赘述了，详见解题报告。其实很简单，自己YY下也可以证明的。）

PS：这题的精度要求虽然只有小数点后3位，但是由于大量的计算，实际对精度的要求很高，因此对采用的算法也有一点要求。

#include <cstdio>
#include <cmath>
const int maxn = 1010;
const double PI = acos(-1.0);
const double eps = 1e-9;

int T, cas = 1, n;
double r, a[maxn], b[maxn], c[maxn];
double area[maxn], height[maxn];

double f(double h)
{
double ret = 0;
for (int i=1;i<=n;i++)
if (h < height[i]) ret += a[i] * (1.0 - h / height[i]);
return ret;
}

int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%lf", &n, &r);
for (int i=1;i<=n;i++) scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);
for (int i=1;i<=n;i++)
{
double p = (a[i] + b[i] + c[i]) / 2;
area[i] = sqrt(p * (p-a[i]) * (p-b[i]) * (p-c[i]));
height[i] = area[i] * 2 / a[i];
}
double low = 0, high = 100000, mid;
int tt = 60;
while (tt--)
{
mid = (low + high) / 2;
if (f(mid) <= r) high = mid;
else low = mid;
}
double ans = 0, h = mid;
for (int i=1;i<=n;i++)
if (h < height[i]) ans += area[i] - h*a[i]*(h/height[i])/2;
printf("Case #%d: %.3lf\n", cas++, ans);
}
return 0;
}