函数截距的转化 + 凸包的性质
思路
先变形：
$$
\begin{aligned}
& 对于攻击为 atk, 防御为 dnf 的妖怪, 他在环境 a, b 中战斗力为: \\
& f(a, b) = atk + dnf * \frac{a}{b} + dnf + atk * \frac{b}{a} \\
& 设 t = \frac{b}{a}, 有: \\
& f(t) = atk + dnf * \frac{1}{t} + dnf + atk * t \\
& \ge atk + dnf + 2 \sqrt{atk * dnf} \\
& 当且仅当 t = \sqrt{\frac{atk}{dnf}} 时取等
\end{aligned}
$$
这好像还是没法做，因为我们取一个 $t$ 使得这个妖怪最小了，别的妖怪可能就大了，我们考虑把妖怪当作平面中的点，用一条直线的某种信息来表示 $f(t)$ 和对应的 $t$ ，考虑构造直线 $y = -t * x + b$ ，这个直线在两个坐标轴上的截距是 $\frac{b}{t}$ 和 $b$ ，你直接看好像没啥，但取 $b = dnf + atk * t$ ，那么 $\frac{b}{t} = atk + dnf * \frac{1}{t}$ ，发现 $b + \frac{b}{t}$ 就是 $f(t)$ ，而更另我们兴奋的是，此时 $b$ 的取值恰好保证直线 $y = -t * x + b$ 过点 $(atk, dnf)$
于是问题转化为：给定平面上 $n$ 个点，求一个斜率使过每个点的斜率为 $-t$ 的直线在两个坐标轴上的截距之和最大值最小（好绕），然后我们不难发现，只有凸包上的点可能贡献答案，因为对于任意一个不是凸包上的点，不管斜率取多少，你总可以向“外”平移该直线直到它与凸包相切，此时截距之和一定变大，而且只有上凸壳会贡献；而对于凸包上的点，我们只要计算出那个对应的 $t$ 跟新答案即可，如果无法取到，即 $t$ 对应的直线不与凸包相切而是相交，就取满足的最近的值，由对勾函数的单调性正确性显然
#define fi first
#define se second
using DB = double;
using PDD = std::pair<double, double>;
const int N = 1e6 + 100;
const DB eps = 1e-6, INF = 0x3f3f3f3f;
int n, stk[N], top;
PDD a[N];
DB ans = INF;
int cmp(DB x, DB y)
{
if (std::fabs(x - y) < eps) return 0;
return x > y ? 1 : -1;
}
PDD operator - (PDD x, PDD y){ return {x.fi - y.fi, x.se - y.se}; }
DB operator * (PDD x, PDD y){ return x.fi * y.se - x.se * y.fi; }
DB get_k(PDD x, PDD y)
{
if (!cmp(x.fi, y.fi)) return INF;
return (x.se - y.se) / (x.fi - y.fi);
}
DB area(PDD x, PDD y, PDD z){ return (y - x) * (z - x); }
void convex(PDD *x, int n)
{
std::sort(x, x + n);
top = 0;
for (int i = 0; i < n; ++i)
{
while (top >= 2 && cmp(area(x[stk[top - 2]], x[stk[top - 1]], x[i]), 0) >= 0) --top;
stk[top++] = i;
}
}
DB calc(PDD x, DB k)
{
if (cmp(k, 0) <= 0) return INF;
return x.fi + x.se + x.fi * k + x.se / k;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%lf %lf", &a[i].fi, &a[i].se);
convex(a, n);
for (int i = 0; i < top; ++i)
{
PDD p = a[stk[i]], lp = a[stk[(i - 1 + top) % top]], rp = a[stk[(i + 1) % top]];
DB t = std::sqrt(p.se / p.fi), kl = get_k(lp, p), kr = get_k(p, rp);
if ((i == 0 || cmp(-t, kl) <= 0) && (i == top - 1 || cmp(-t, kr) >= 0)) ans = std::min(ans, calc(p, t));
else if (i > 0) ans = std::min(ans, calc(p, -kl));
else if (i < top - 1) ans = std::min(ans, calc(p, -kr));
}
if (!cmp(ans, 0)) ans = 0;
printf("%.4lf\n", ans);
return 0;
}