Description

给定 $n$ 个直角三角形，第 $i$ 个三角形的斜边长度为 $r_i$。
设该三角形的一条直角边为 $h_i$（称为高度），另一条直角边为 $w_i$，则有：

$$h_i^2 + w_i^2 = r_i^2$$

该三角形的面积为：

$$A_i = \frac12 h_i w_i = \frac12 h_i \sqrt{r_i^2 - h_i^2}$$

在满足约束条件

$$\sum_{i=1}^n h_i \le S,\quad h_i \ge 0$$

的前提下，求所有三角形面积之和的最大值。

Analysis

Step 1

对固定的斜边长度 $r$，定义面积函数：

$$f_r(h) = \frac12 h\sqrt{r^2 - h^2}$$

当 $h \in \left[0, \frac{r}{\sqrt2}\right]$ 时，有：

• $f_r(h)$ 单调递增；
• $f_r(h)$ 为严格凹函数；
• 最大值在 $h=\frac{r}{\sqrt2}$ 处取得；
• 最大面积为 $\frac{r^2}{4}$。

其导数为：

$$f_r'(h) = \frac{r^2 - 2h^2}{2\sqrt{r^2 - h^2}}$$

在区间 $\left[0, \frac{r}{\sqrt2}\right]$ 上，
$f_r'(h)$ 从 $\frac r2$ 单调下降到 $0$。

---

Step 2

若满足：

$$S \ge \sum_{i=1}^n \frac{r_i}{\sqrt2}$$

则可以让每个三角形都取到最大面积，此时剩余高度不会再产生贡献。

答案直接为：

$$\sum_{i=1}^n \frac{r_i^2}{4}$$

后续只需考虑 $S$ 不足的情况。

当 $S$ 不足以让所有三角形达到最大面积时， 最优解必然满足高度约束是紧的：

$$\sum_{i=1}^n h_i = S$$

构造拉格朗日函数：

$$L = \sum_{i=1}^n f_{r_i}(h_i) - \lambda\left(\sum_{i=1}^n h_i - S\right)$$

对每个 $h_i$ 求偏导并令其为零，可得最优性条件：

$$f_{r_i}'(h_i) = \lambda$$

这意味着： 在最优解中，每个三角形的“单位高度带来的边际面积收益”是相同的。

Step 3

由条件：

$$\frac{r^2 - 2h^2}{2\sqrt{r^2 - h^2}} = \lambda$$

设：

$$t = \sqrt{r^2 - h^2}$$

可化为一元二次方程：

$$2t^2 + 2\lambda t - r^2 = 0$$

取正根：

$$t = \frac{\lambda + \sqrt{\lambda^2 + 2r^2}}{2}$$

于是：

$$h = \sqrt{r^2 - t^2}$$

当 $\lambda \ge \frac r2$ 时，最优解为 $h=0$。

---

Step 4

对于固定的 $r$，$h(\lambda)$ 随 $\lambda$ 单调递减， 因此：

$$H(\lambda) = \sum_{i=1}^n h_i(\lambda)$$

也是单调递减函数。

可以在区间：

$$[0,\ \max(r_i)/2]$$

内对 $\lambda$ 进行二分， 寻找满足 $H(\lambda)=S$ 的值。

可以证明二分次数不大于 $100$ 次。

确定 $\lambda$ 后：

1. 对每个三角形计算对应的最优高度 $h_i$；
2. 累加面积：

$$\sum_{i=1}^n \frac12 h_i \sqrt{r_i^2 - h_i^2}$$

即为所求答案。

Code

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>

using ll = long long int;
using ld = long double;
static constexpr int MAXN = 1e5 + 10;

int n;

ld max_r, S, r[MAXN];

inline ld best_h(ld R, ld lambda) {
	if (lambda >= R * 0.5) return 0.0;
	
	ld disc = lambda * lambda + 2.0 * R * R;
	ld t = (lambda + std::sqrt(disc)) * 0.5;
	
	ld x = R * R - t * t;
	if (x <= 0.0L) return 0.0;
	ld h = std::sqrt(x);
	
	ld cap = R / std::sqrt(2.0);
	if (h > cap) h = cap;
	return h;
}

inline ld area(ld R, ld h) {
	ld t2 = R * R - h * h;
	if (t2 <= 0.0) return 0.0;
	return 0.5 * h * std::sqrt(t2);
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	std::cin >> n >> S;
	
	for (int i = 1; i <= n; ++i) {
		std::cin >> r[i];
		max_r = std::max(max_r, r[i]);
	}
	
	ld sum_cap = 0.0;
	ld maxS = 0.0;
	
	for (int i = 1; i <= n; ++i) {
		sum_cap += r[i] / std::sqrt(2.0L);
		maxS += (r[i] * r[i]) * 0.25L;
	}
	
	std::cout << std::fixed << std::setprecision(10);
	
	if (S >= sum_cap) {
		std::cout << maxS;
		return 0;
	}
	
	ld ql = 0.0, qr = max_r * 0.5;
	for (int it = 1; it <= 120; ++it) {
		ld mid = (ql + qr) * 0.5;
		
		ld totH = 0.0;
		for (int i = 1; i <= n; ++i) totH += best_h(r[i], mid);
		
		if (totH > S) ql = mid;
		else qr = mid;
	}
	
	ld lambda = qr;
	ld ans = 0.0L;
	for (int i = 1; i <= n; ++i) {
		ld h = best_h(r[i], lambda);
		ans += area(r[i], h);
	}
	
	std::cout << ans;
	
	
	return 0;
}