8570: BZOJ4570:[Scoi2016]妖怪

Memory Limit:64 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

邱老师是妖怪爱好者,他有n只妖怪,每只妖怪有攻击力atk和防御力dnf两种属性。邱老师立志成为妖怪大师,于 是他从真新镇出发,踏上未知的旅途,见识不同的风景。环境对妖怪的战斗力有很大影响,在某种环境中,妖怪可 以降低自己k×a点攻击力,提升k×b点防御力或者,提升自己k×a点攻击力,降低k×b点防御力,a,b属于正实数 ,k为任意实数,但是atk和dnf必须始终非负。妖怪在环境(a,b)中的战斗力为妖怪在该种环境中能达到的最大攻击 力和最大防御力之和。strength(a,b)=max(atk(a,b))+max(dnf(a,b))环境由a,b两个参数定义,a,b的含义见前 文描述。比如当前环境a=3,b=2,那么攻击力为6,防御力为2的妖怪,能达到的最大攻击力为9,最大防御力为6。 所以该妖怪在a=3,b=2的环境下战斗力为15。因此,在不同的环境,战斗力最强的妖怪可能发生变化。作为一名优 秀的妖怪训练师,邱老师想发掘每一只妖怪的最大潜力,他想知道在最为不利的情况下,他的n只妖怪能够达到的 最强战斗力值,即存在一组正实数(a,b)使得n只妖怪在该环境下最强战斗力最低。


输入格式

第一行一个n,表示有n只妖怪。接下来n行,每行两个整数atk和dnf,表示妖怪的攻击力和防御力。 1≤n≤10^6, 0<atk,dnf≤10^8


输出格式

 输出在最不利情况下最强妖怪的战斗力值,保留4位小数。


样例输入

3 
1 1 
1 2 
2 2

样例输出

8.0000

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: