P3291 [SCOI2016] Monster

Teacher Qiu is a monster enthusiast. He has $n$ monsters, each with two attributes: attack $\mathrm{atk}$ and defense $\mathrm{dnf}$. Determined to become a master of monsters, he sets off from Zhenxin Town on an unknown journey to see different sceneries. The environment $(a, b)$ is defined by two parameters $a$ and $b$, where $a$ and $b$ are positive real numbers. In environment $(a, b)$, a monster may decrease its attack by $k \times a$ and increase its defense by $k \times b$, or increase its attack by $k \times a$ and decrease its defense by $k \times b$. Here $k$ can be any real number, but $\mathrm{atk}$ and $\mathrm{dnf}$ must always remain non-negative. In environment $(a, b)$, the monster’s strength $\mathrm{strength}$ is defined as the sum of the maximum attack it can achieve and the maximum defense it can achieve in that environment, i.e., $\mathrm{strength}(a,b)=\max(\mathrm{atk}(a,b))+\max(\mathrm{dnf}(a,b))$. For example, if the current environment has $a=3$, $b=2$, then for a monster with attack $6$ and defense $2$, the maximum achievable attack is $9$ and the maximum achievable defense is $6$. Therefore, this monster’s strength in the environment $a=3$, $b=2$ is $15$. Thus, the strongest monster may change in different environments. As an excellent monster trainer, Teacher Qiu wants to discover each monster’s maximum potential. He wants to know, in the most unfavorable case, the strongest strength value that his $n$ monsters can achieve. In other words, there exists a pair of positive real numbers $(a, b)$ such that the strongest strength among the $n$ monsters in that environment is minimized; you need to output this minimum strength.

The first line contains an integer $n$, the number of monsters. Each of the next $n$ lines contains two integers $\mathrm{atk}_i$ and $\mathrm{dnf}_i$, denoting the attack and defense of the $i$-th monster.

Output the strongest monster’s strength value in the most unfavorable case, with $4$ digits after the decimal point.

Constraints: For $100\%$ of the testdata, $1 \le n \le 10^6$, $0 \lt \mathrm{atk}, \mathrm{dnf} \le 10^8$. Statement fixed by Starrykiller. Translated by ChatGPT 5