4215. 博彩游戏

【题目描述】

运气是博彩游戏的核心要素。有些人通过精准掌握投注标的来提升胜率和收益。

我们换个思路：不同博彩公司对同一结果会给出不同赔率（赔率x表示，若押注1欧元且预测正确，可获得x欧元回报；预测错误则无利可图。注意：无论结果如何，你都需支付1欧元本金）。若能通过巧妙组合多注实现稳赚，你自然希望最大化这种稳赚利润。

假设某赛事存在两种可能结果，n家博彩公司提供不同赔率。记第i家博彩公司对第一种结果的赔率为ai，第二种结果的赔率为bi。你可以选择任意组合的赔率进行投注，甚至可在同一家公司同时押注两种结果。但所有投注金额必须严格为1欧元，且不能在同一家公司重复押注同一结果。对于第一种结果，你将从所有押注该结果的博彩公司获得ai欧元；同理，第二种结果则从所有符合条件的博彩公司获得bi欧元。当然，两种情况下的本金均为1欧元。那么，若能最优组合所有投注，你将获得的最大稳赚利润（即无论结果如何）是多少？

【输入格式】

首行为博彩公司数量n。后续n行分别列出各博彩公司提供的赔率，每个赔率由两个空格分隔的实数ai和bi表示——ai为i家博彩公司对第一种结果的赔率，bi为第二种结果的赔率。所有赔率均保留最多4位小数。

第一行一个正整数 n ，表示博彩公司数量。

接下来 n 行每行两个空格隔开的实数 Ai,Bi。分别表示各博彩公司提供的赔率，每个赔率由两个空格分隔的实数ai和bi表示——ai为i家博彩公司对第一种结果的赔率，bi为第二种结果的赔率。输入的实数不会超过四位小数。

【输出格式】

输出输出最大保证利润，请输出到小数点后恰好四位。

【样例输入】

4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5 

【样例输出】

0.5000

【样例说明】

最优投注策略是：

在第一家博彩公司押注第二结果，在第三和第四家博彩公司押注第一结果。

若第一结果出现，可获利1.6 + 1.9 − 3 = 0.5欧元；若第二结果出现，则获利3.7 − 3 = 0.7欧元。

因此，无论结果如何，我们都能确保获得0.5欧元的收益。

【数据规模与约定】

大样例

对于所有测试点，有 1.0≤Ai,Bi≤1000.0，0≤n≤10^5。

对于测试点1-6，n<=10

对于测试点7-16，n<=1000

对于测试点17-25，n<=10^5

【来源】

在此键入。